The fitness consequences of deleterious mutations are sometimes greater when individuals are parasitized, hence parasites may result in the more rapid purging of deleterious mutations from host populations. The significance of host deleterious mutations when hosts and parasites antagonistically coevolve (reciprocal evolution of host resistance and parasite infectivity) has not previously been experimentally investigated. We addressed this by coevolving the bacterium Pseudomonas fluorescens and a parasitic bacteriophage in laboratory microcosms, using bacteria with high and low mutation loads. Directional coevolution between bacterial resistance and phage infectivity occurred in all populations. Bacterial population fitness, as measured by competition experiments with ancestral genotypes in the absence of phage, declined with time spent coevolving. However, this decline was significantly more rapid in bacteria with high mutation loads, suggesting the cost of bacterial resistance to phage was greater in the presence of deleterious mutations (synergistic epistasis). As such, resistance to phage was more costly to evolve in the presence of a high mutation load. Consistent with these data, bacteria with high mutation loads underwent less rapid directional coevolution with their phage populations, and showed lower levels of resistance to their coevolving phage populations. These data suggest that coevolution with parasites increases the rate at which deleterious mutations are purged from host populations.