Host–parasite co-evolutionary studies can shed light on diversity and the processes that shape it. Molecular methods have proven to be an indispensable tool in this task, often uncovering unseen diversity. This study used two nuclear markers (18S rRNA and 28S rRNA) and one mitochondrial (cytochrome oxidase subunit I) marker to investigate the diversity of nematodes of the family Pharyngodonidae parasitizing New Zealand (NZ) lizards (lygosomine skinks and diplodactylid geckos) and to explore their co-evolutionary history. A Bayesian approach was used to infer phylogenetic relationships of the parasitic nematodes. Analyses revealed that nematodes parasitizing skinks, currently classified as Skrjabinodon, are more closely related to Spauligodon than to Skrjabinodon infecting NZ geckos. Genetic analyses also uncovered previously undetected diversity within NZ gecko nematodes and provided evidence for several provisionally cryptic species. We also examined the level of host–parasite phylogenetic congruence using a global-fit approach. Significant congruence was detected between gecko-Skrjabinodon phylogenies, but our results indicated that strict co-speciation is not the main co-evolutionary process shaping the associations between NZ skinks and geckos and their parasitic nematodes. However, further sampling is required to fully resolve co-phylogenetic patterns of diversification in this host–parasite system.