Host-parasite interactions exert strong selection pressures on the genomes of both host and parasite. These interactions can lead to negative frequency-dependent selection, a form of balancing selection that is hypothesised to explain the high levels of polymorphism seen in many host immune and parasite antigen loci. Here, we sequence the genomes of several individuals of Heligmosomoides bakeri, a model parasite of house mice, and Heligmosomoides polygyrus, a closely related parasite of wood mice. Although H. bakeri is commonly referred to as H. polygyrus in the literature, their genomes show levels of divergence that are consistent with at least a million years of independent evolution. The genomes of both species contain hyper-divergent haplotypes that are enriched for proteins that interact with the host immune response. Many of these haplotypes originated prior to the divergence between H. bakeri and H. polygyrus, suggesting that they have been maintained by long-term balancing selection. Together, our results suggest that the selection pressures exerted by the host immune response have played a key role in shaping patterns of genetic diversity in the genomes of parasitic nematodes.