Attempts to reconstruct the phylogenetic history of the Anopheles gambiae cryptic species complex have yielded strongly conflicting results. In particular, An. gambiae, the primary African malaria vector, is variously placed as a sister taxon to either Anopheles arabiensis or Anopheles merus. The recent divergence times for members of this complex complicate phylogenetic analysis, making it difficult to unambiguously implicate interspecific gene flow, versus retained ancestral polymorphism, as the source of conflict. Using sequences at four unlinked loci, which were determined from multiple specimens within each of five species in the complex, we found contrasting patterns of sequence divergence between the X chromosome and the autosomes. The isolation model of speciation assumes a lack of gene flow between species since their separation. This model could not be rejected for An. gambiae and An. arabiensis, although the data fit the model poorly. On the other hand, evidence from gene trees supports genetic introgression of chromosome 2 inversions between An. gambiae and An. arabiensis, and also points to more broad scale genetic exchange of autosomal sequences between this species pair. That such exchange has been relatively recent is suggested not only by the lack of fixed differences at three autosomal loci but also by the sharing of full haplotypes at two of the three loci, which is in contrast to several fixed differences and considerably deeper divergence on the X. The proposed acquisition by An. gambiae of sequences from the more arid-adapted An. arabiensis may have contributed to the spread and ecological dominance of this malaria vector.