Anopheles gambiae Giles s.s. and Anopheles arabiensis Patton (Diptera: Culicidae) are major vectors of malaria in Nigeria. We used 1115 bp of the mitochondrial COI gene to assess their population genetic structures based on samples from across Nigeria (n = 199). The mtDNA neighbour-joining tree, based on F(ST) estimates, separated An. gambiae M and S forms, except that samples of An. gambiae M from Calabar clustered with all the An. gambiae S form. Anopheles arabiensis and An. gambiae could be combined into a single star-shaped, parsimonious haplotype network, and shared three haplotypes. Haplotype diversity values were high in An. arabiensis and An. gambiae S, and intermediate in An. gambiae M; all nucleotide diversities were relatively low. Taken together, patterns of haplotype diversity, the star-like genealogy of haplotypes, five of seven significant neutrality tests, and the violation of the isolation-by-distance model indicate population expansion in An. arabiensis and An. gambiae S, but the signal was weak in An. gambiae M. Selection is supported as an important factor shaping genetic structure in An. gambiae in Nigeria. There were two geographical subdivisions in An. arabiensis: one included all southern localities and all but two central localities; the other included all northern and two central localities. Re-analysing an earlier microsatellite dataset of An. arabiensis using a Bayesian method determined that there were two distinctive clusters, northern and southern, that were fairly congruent with the mtDNA subdivisions. There was a trend towards decreasing genetic diversity in An. arabiensis from the northern savannah to the southern rainforest that corroborated previous data from microsatellites and polytene chromosomes.