We present a phylogeographic study of at least six reproductively isolated lineages of new world harvester ants within the Pogonomyrmex barbatus and P. rugosus species group. The genetic and geographic relationships within this clade are complex: Four of the identified lineages show genetic caste determination (GCD) and are divided into two pairs. Each pair has evolved under a mutualistic system that necessitates sympatry. These paired lineages are dependent upon one another because their GCD requires interlineage matings for the production of F1 hybrid workers, and intralineage matings are required to produce queens. This GCD system maintains genetic isolation among these interdependent lineages, while simultaneously requiring co-expansion and emigration as their distributions have changed over time. It has also been demonstrated that three of these four GCD lineages have undergone historical hybridization, but the narrower sampling range of previous studies has left questions on the hybrid parentage, breadth, and age of these groups. Thus, reconstructing the phylogenetic and geographic history of this group allows us to evaluate past insights and hypotheses and to plan future inquiries in a more complete historical biogeographic context. Using mitochondrial DNA sequences sampled across most of the morphospecies’ ranges in the U.S.A. and Mexico, we conducted a detailed phylogeographic study. Remarkably, our results indicate that one of the GCD lineage pairs has experienced a dramatic range expansion, despite the genetic load and fitness costs of the GCD system. Our analyses also reveal a complex pattern of vicariance and dispersal in Pogonomyrmex harvester ants that is largely concordant with models of late Miocene, Pliocene, and Pleistocene range shifts among various arid-adapted taxa in North America.