Antagonistic coevolution between hosts and parasites can lead to local adaptation (LA), such that parasite fitness is greatest in sympatric hosts (or vice versa). The magnitude of LA typically increases with geographic distance, which is assumed to be because genetic (and hence phenotypic) distance increases with geographic distance. Here we explicitly test the relationships between parasite genetic and phenotypic distance and LA using isolates of coevolved viral parasites (lytic bacteriophage ϕ2) and the host bacterium Pseudomonas fluorescens SBW25. We find positive relationships between parasite genotype and infectivity phenotype, but the strength of the relationship was greater when infectivity was defined by the identity of hosts that could be infected rather than the actual number of hosts infected (host range), and when measurements were compared within rather than among populations. Crucially, we find a monotonic relationship between LA and genetic distance across phage isolates from different populations, although in contrast to many geographic studies, parasite LA decreased with genetic distance. These results can be explained by the fact that bacteria can rapidly adapt to phage infectivity mutations, but that evolved resistance has a degree of specificity to the local phage population. Our results show that antagonistic coevolution alone can result in predictable links between genetic distance and host-parasite local adaptation.