The Quaternary climate cycles forced species to repeatedly migrate across a continually changing landscape. How these shifts in distribution impacted the evolution of unrelated but ecologically associated taxa has remained elusive due to the stochastic nature of the evolutionary process and variation in species-specific biological characteristics and environmental constraints. To account for the uncertainty in genealogical estimates, we adopted a coalescent approach for testing hypotheses of population divergence in coevolving taxa. We compared genealogies of a specialized herbivorous insect, Parnassius smintheus (Papilionidae), and its host plant, Sedum lanceolatum (Crassulaceae), from the alpine tundra of the Rocky Mountains to null distributions from coalescent simulations to test whether tightly associated taxa shared a common response to the paleoclimatic cycles. Explicit phylogeographic models were generated from geologic and biogeographic data and evaluated over a wide range of divergence times given calibrated mutation rates for both species. Our analyses suggest that the insect and its host plant responded similarly but independently to the climate cycles. By promoting habitat expansion and mixing among alpine populations, glacial periods repeatedly reset the distributions of genetic variation in each species and inhibited continual codivergence among pairs of interacting species.