Anopheles arabiensis and Anopheles gambiae s.s. are found sympatrically throughout Nigeria, with An. arabiensis more common in the dry savannah of the North and An. gambiae prevalent in the wet forest of the South. However, drought for the past several decades, destruction of forested areas, and urbanization have changed the habitat of these two major malaria vectors in Nigeria. To assess current gene flow and historical changes in population structures, nested clade analyses were performed using sequence data from an approximately 1100 base pair region of the cytochrome oxidase I mitochondrial gene. More haplotypes (variant sequences) were found among populations of An. gambiae than An. arabiensis. The M and S molecular forms of An. gambiae were also compared, with S forms found to be more variable than M forms. We detected two shared haplotypes between the M and S forms. An. arabiensis and An. gambiae shared 3 haplotypes, suggestive of a hypervariable region or possible introgression. All of the haplotypes between and within species could be connected parsimoniously. Several clades of An. arabiensis and of An. gambiae indicated restricted gene flow with isolation by distance. In addition, two clades of An. arabiensis suggested contiguous range expansion.