Phenotypically diverse Lake Malawi cichlids exhibit similar genomes. The extensive sharing of genetic polymorphism among forms has both intrigued and frustrated biologists trying to understand the nature of diversity in this and other rapidly evolving systems. Shared polymorphism might result from hybridization and/or the retention of ancestrally polymorphic alleles. To examine these alternatives, we used new genomic tools to characterize genetic differentiation in widespread, geographically structured populations of Labeotropheus fuelleborni and Metriaclima zebra. These phenotypically distinct species share mitochondrial DNA (mtDNA) haplotypes and show greater mtDNA differentiation among localities than between species. However, Bayesian analysis of nuclear single nucleotide polymorphism (SNP) data revealed two distinct genetic clusters corresponding perfectly to morphologically diagnosed L. fuelleborni and M. zebra. This result is a function of the resolving power of the multi-locus dataset, not a conflict between nuclear and mitochondrial partitions. Locus-by-locus analysis showed that mtDNA differentiation between species (F(CT)) was nearly identical to the median single-locus SNP F(CT). Finally, we asked whether there is evidence for gene flow at sites of co-occurrence. We used simulations to generate a null distribution for the level of differentiation between co-occurring populations of L. fuelleborni and M. zebra expected if there was no hybridization. The null hypothesis was rejected for the SNP data; populations that co-occur at rock reef sites were slightly more similar than expected by chance, suggesting recent gene flow. The coupling of numerous independent markers with extensive geographic sampling and simulations utilized here provides a framework for assessing the prevalence of gene flow in recently diverged species.