Population genetic structures of the two major malaria vectors Anopheles gambiae s.s. and An. arabiensis, differ markedly across Sub-Saharan Africa, which could reflect differences in historical demographies or in contemporary gene flow. Elucidation of the degree and cause of population structure is important for predicting the spread of genetic traits such as insecticide resistance genes or artificially engineered genes. Here the population genetics of An. gambiae s.s. and An. arabiensis in the central, eastern and island regions of Tanzania were compared. Microsatellite markers were screened in 33 collections of female An. gambiae s.l., originating from 22 geographical locations, four of which were sampled in two or three years between 2008 and 2010. An. gambiae were sampled from six sites, An. arabiensis from 14 sites, and both species from two sites, with an additional colonised insectary sample of each species. Frequencies of the knock-down resistance (kdr) alleles 1014S and 1014F were also determined. An. gambiae exhibited relatively high genetic differentiation (average pairwise FST = 0.131), significant even between nearby samples, but without clear geographical patterning. In contrast, An. arabiensis exhibited limited differentiation (average FST = 0.015), but strong isolation-by-distance (Mantel test r = 0.46, p = 0.0008). Most time-series samples of An. arabiensis were homogeneous, suggesting general temporal stability of the genetic structure. An. gambiae populations from Dar es Salaam and Bagamoyo were found to have high frequencies of kdr 1014S (around 70%), with almost 50% homozygote but was at much lower frequency on Unguja Island, with no. An. gambiae population genetic differentiation was consistent with an island model of genetic structuring with highly restricted gene flow, contrary to An. arabiensis which was consistent with a stepping-stone model of extensive, but geographically-restricted gene flow.