We estimated current and long-term effective population size (Ne) of two Anopheles gambiae (savanna cytotype) populations in Kenya. Temporal variation at nine microsatellite loci in each population sampled 7 and 9 years apart and genetic diversity in each sample were analyzed to answer the following questions. (1) Do bottlenecks occur in Kenyan populations of A. gambiae? (2) How variable are different populations with respect to their current and long-term Ne values? (3) What are the implications of these results on population structure and history? The estimates of Ne of Asembo and Jego were 6,359 and 4,258, respectively, and the lower 95% limits were 2,455 and 1,669, respectively. Thus, despite the typical observation of low density at the village level during the dry season, large populations are maintained annually. Large current Ne is consistent with previous studies showing low differentiation across the continent, especially under Wright's isolation-by-distance model. Current Ne in Asembo was 1.5-fold higher than in Jego, but this difference was not significant. Long-term Ne in Asembo (22,667) was 2.9-fold higher than that in Jego (7,855) based on the stepwise mutation model. The difference between populations was significant at both time points regardless of whether long-term Ne values were calculated based on the stepwise mutation model or the infinite-alleles model. Heterozygosity in Jego declined significantly between 1987 (59%) and 1996 (54%), whereas heterozygosity in Asembo was stable (66%-65%). Despite the relatively high and significant differentiation between Asembo and Jego (FST = 0.072-0.10, RST = 0.037-0.038), all alleles in Jego were found in Asembo but not vice versa. All of these findings suggest that lower Ne in Jego magnifies differentiation between the two populations. The long-term Ne was biased downward, because its calculation was based on an upper bound estimate of microsatellite mutation rate. Ne values based on mtDNA and allozymes were an order of magnitude higher. Long-term Ne therefore, is probably measured in hundreds of thousands and hence does not support a recent expansion of this species from a small population.