Studies of antagonistic coevolution between hosts and parasites typically focus on resistance and infectivity traits. However, coevolution could also have genome-wide effects on the hosts due to pleiotropy, epistasis, or selection for evolvability. Here, we investigate these effects in the bacterium Pseudomonas fluorescens SBW25 during approximately 400 generations of evolution in the presence or absence of bacteriophage (coevolution or evolution treatments, respectively). Coevolution resulted in variable phage resistance, lower competitive fitness in the absence of phages, and greater genome-wide divergence both from the ancestor and between replicates, in part due to the evolution of increased mutation rates. Hosts from coevolution and evolution treatments had different suites of mutations. A high proportion of mutations observed in coevolved hosts were associated with a known phage target binding site, the lipopolysaccharide (LPS), and correlated with altered LPS length and phage resistance. Mutations in evolved bacteria were correlated with higher fitness in the absence of phages. However, the benefits of these growth-promoting mutations were completely lost when these bacteria were subsequently coevolved with phages, indicating that they were not beneficial in the presence of resistance mutations (consistent with negative epistasis). Our results show that in addition to affecting genome-wide evolution in loci not obviously linked to parasite resistance, coevolution can also constrain the acquisition of mutations beneficial for growth in the abiotic environment.