Disentangling the processes and mechanisms underlying adaptive diversification is facilitated by the comparative study of replicate population pairs that have diverged along a similar environmental gradient. Such a setting is realized in a cichlid fish from southern Lake Tanganyika, Astatotilapia burtoni, which occurs within the lake proper as well as in various affluent rivers. Previously, we demonstrated that independent lake and stream populations show similar adaptations to the two habitat regimes. However, little is known about the evolutionary and demographic history of the A. burtoni populations in question and the patterns of genome divergence among them. Here, we apply restriction site-associated DNA sequencing (RADseq) to examine the evolutionary history, the population structure and genomic differentiation of lake and stream populations in A. burtoni. A phylogenetic reconstruction based on genome-wide molecular data largely resolved the evolutionary relationships among populations, allowing us to re-evaluate the independence of replicate lake-stream population clusters. Further, we detected a strong pattern of isolation by distance, with baseline genomic divergence increasing with geographic distance and decreasing with the level of gene flow between lake and stream populations. Genome divergence patterns were heterogeneous and inconsistent among lake-stream population clusters, which is explained by differences in divergence times, levels of gene flow and local selection regimes. In line with the latter, we only detected consistent outlier loci when the most divergent lake-stream population pair was excluded. Several of the thus identified candidate genes have inferred functions in immune and neuronal systems and show differences in gene expression between lake and stream populations.