The Great Lakes region of East Africa, including Lake Victoria, is the center of diversity of the mega-diverse cichlid fishes (Perciformes: Teleostei). Paleolimnological evidence indicates dramatic desiccation of this lake ca. 18,000-15,000 years ago. Consequently, the hundreds of extant endemic haplochromine species in the lake must have either evolved since then or refugia must have existed, within that lake basin or elsewhere, from which Lake Victoria was recolonized. We studied the population history of the Lake Victoria region superflock (LVRS) of haplochromine cichlids based on nuclear genetic analysis (12 microsatellite loci from 400 haplochomines) of populations from Lake Kivu, Lake Victoria, and the connected and surrounding rivers and lakes. Population genetic analyses confirmed that Lake Kivu haplochromines colonized Lake Victoria. Coalescent analyses show a 30- to 50-fold decline in the haplochromine populations of Lake Victoria, Lake Kivu, and the region ca. 18,000-15,000 years ago. We suggest that this coincides with drastic climatic and geological changes in the late Pleistocene. The most recent common ancestor of the Lake Victoria region haplochromines was estimated to have existed about 4.5 million years ago, which corresponds to the first radiation of cichlids in Lake Tanganyika and the origin of the tribe Haplochrominii. This relatively old evolutionary origin may explain the high levels of polymorphism still found in modern haplochromines. This degree of polymorphism might have acted as a "genetic reservoir" that permitted the explosive radiation of hundreds of haplochromines and their array of contemporary adaptive morphologies.