We estimated the effective population sizes (Ne) and tested for short-term temporal demographic stability of populations of two Lake Malawi cichlids: Maylandia benetos, a micro-endemic, and Maylandia zebra, a widespread species found across the lake. We sampled a total of 351 individuals, genotyped them at 13 microsatellite loci and sequenced their mitochondrial D-loop to estimate genetic diversity, population structure, demographic history and effective population sizes. At the microsatellite loci, genetic diversity was high in all populations. Yet, genetic diversity was relatively low for the sequence data. Microsatellites yielded mean Ne estimates of 481 individuals (±99 SD) for M. benetos and between 597 (±106.3 SD) and 1524 (±483.9 SD) individuals for local populations of M. zebra. The microsatellite data indicated no deviations from mutation–drift equilibrium. Maylandia zebra was further found to be in migration–drift equilibrium. Temporal fluctuations in allele frequencies were limited across the sampling period for both species. Bayesian Skyline analyses suggested a recent expansion of M. zebra populations in line with lake-level fluctuations, whereas the demographic history of M. benetos could only be estimated for the very recent past. Divergence time estimates placed the origin of M. benetos within the last 100 ka after the refilling of the lake and suggested that it split off the sympatric M. zebra population. Overall, our data indicate that micro-endemics and populations in less favourable habitats have smaller Ne, indicating that drift may play an important role driving their divergence. Yet, despite small population sizes, high genetic variation can be maintained.