The myxozoan parasite Ceratonova shasta is an important pathogen that infects multiple species of Pacific salmonids. Ongoing genetic surveillance has revealed stable host-parasite relationships throughout the parasite's endemic range. We applied Bayesian phylogenetics to test specific hypotheses about the evolution of these host-parasite relationships within the well-studied Klamath River watershed in Oregon and California, USA. The results provide statistical support that different genotypes of C. shasta are distinct lineages of one species, which is related to two other Ceratonova species in the same ecosystems; Ceratonova X in speckled dace and C. gasterostea in threespine stickleback. Furthermore, we found strong support for the hypothesis that C. shasta type 0 in native steelhead trout and type I in Chinook salmon each evolved with a specialist host adaptation strategy, while C. shasta type II in coho salmon resulted from a generalist host adaptation strategy. Inferred date and host species of the most recent common ancestor of extant Klamath basin types indicate that it occurred between 14,000 and 21,000 years ago, and most likely infected a native steelhead or rainbow trout host.