Anopheles melas is a brackish water-breeding member of the An. gambiae complex that is distributed along the coast of West Africa and is a major malaria vector within its range. Because little is known about the population structure of this species, we analyzed 15 microsatellite markers and 1,161 bp of mtDNA in 11 An. melas populations collected throughout its range. Compared to its sibling species An. gambiae, An. melas populations have a high level of genetic differentiation between them, representing its patchy distribution due to its fragmented larval habitat which is associated with mangroves and salt marsh grass. Populations clustered into three distinct groups representing Western Africa, Southern Africa, and Bioko Island populations that appear to be mostly isolated. Fixed differences in the mtDNA are present between all three clusters, and a Bayesian clustering analysis of the microsatellite data found no evidence for migration from mainland to Bioko Island populations, and little migration was evident between the Southern to the Western cluster. Surprisingly, mtDNA divergence between the three An. melas clusters is on par with levels of divergence between other species of the An. gambiae complex, and no support for monophyly was observed in a maximum likelihood phylogenetic analysis. Finally, an Approximate Bayesian Analysis of microsatellite data indicates that Bioko Island An. melas populations were connected to the mainland populations in the past, but became isolated, presumably when sea levels rose after the last glaciation period (≥10,000-11,000 years ago). This study has exposed species level genetic divergence within An. melas, and also has implications for control of this malaria vector.