Australian spiny mountain crayfish (Euastacus, Parastacidae) and their ecotosymbiotic temnocephalan flatworms (Temnocephalida, Platyhelminthes) may have co-occurred and interacted through deep time, during a period of major environmental change. Therefore, reconstructing the history of their association is of evolutionary, ecological, and conservation significance. Here, time-calibrated Bayesian phylogenies of Euastacus species and their temnocephalans (Temnohaswellia and Temnosewellia) indicate near-synchronous diversifications from the Cretaceous. Statistically significant cophylogeny correlations between associated clades suggest linked evolutionary histories. However, there is a stronger signal of codivergence and greater host specificity in Temnosewellia, which co-occurs with Euastacus across its range. Phylogeography and analyses of evolutionary distinctiveness (ED) suggest that regional differences in the impact of climate warming and drying had major effects both on crayfish and associated temnocephalans. In particular, Euastacus and Temnosewellia show strong latitudinal gradients in ED and, conversely, in geographical range size, with the most distinctive, northern lineages facing the greatest risk of extinction. Therefore, environmental change has, in some cases, strengthened ecological and evolutionary associations, leaving host-specific temnocephalans vulnerable to coextinction with endangered hosts. Consequently, the extinction of all Euastacus species currently endangered (75%) predicts coextinction of approximately 60% of the studied temnocephalans, with greatest loss of the most evolutionarily distinctive lineages.