The loss of traits is a commonly observed evolutionary pattern in cave organisms, but due to extensive morphological convergence, inferring relationships between cave and surface populations can be difficult. For instance, Astyanax mexicanus (the blind Mexican cavefish) is thought to have repeatedly lost its eyes following colonization of cave environments, but the number of evolutionarily independent invasions of this species into caves remains unclear. Because of these repeated losses, it has become a model organism for studying the genetic basis of phenotypic trait loss. Here we reconstruct a high-resolution phylogeography for A. mexicanus inferred from both mitochondrial DNA and several thousand single nucleotide polymorphisms. We provide novel insight into the origin of cave populations from the Sabinos and Río Subterráneo caves and present evidence that the Sabinos cave population is part of a unique cave lineage unrelated to other A. mexicanus cave populations. Our results indicate A. mexicanus cave populations have at least four independent origins.