Understanding the molecular basis of repeatedly evolved phenotypes can yield key insights into the evolutionary process. Quantifying gene flow between populations is especially important in interpreting mechanisms of repeated phenotypic evolution, and genomic analyses have revealed that admixture occurs more frequently between diverging lineages than previously thought. In this study, we resequenced 47 whole genomes of the Mexican tetra from three cave populations, two surface populations and outgroup samples. We confirmed that cave populations are polyphyletic and two Astyanax mexicanus lineages are present in our data set. The two lineages likely diverged much more recently than previous mitochondrial estimates of 5–7 mya. Divergence of cave populations from their phylogenetically closest surface population likely occurred between ~161 and 191 k generations ago. The favoured demographic model for most population pairs accounts for divergence with secondary contact and heterogeneous gene flow across the genome, and we rigorously identified gene flow among all lineages sampled. Therefore, the evolution of cave-related traits occurred more rapidly than previously thought, and trogolomorphic traits are maintained despite gene flow with surface populations. The recency of these estimated divergence events suggests that selection may drive the evolution of cave-derived traits, as opposed to disuse and drift. Finally, we show that a key trogolomorphic phenotype QTL is enriched for genomic regions with low divergence between caves, suggesting that regions important for cave phenotypes may be transferred between caves via gene flow. Our study shows that gene flow must be considered in studies of independent, repeated trait evolution.