About half of all bacteria carry genes for CRISPR-Cas adaptive immune systems(1), which provide immunological memory by inserting short DNA sequences from phage and other parasitic DNA elements into CRISPR loci on the host genome(2). Whereas CRISPR loci evolve rapidly in natural environments(3,4), bacterial species typically evolve phage resistance by the mutation or loss of phage receptors under laboratory conditions(5,6). Here we report how this discrepancy may in part be explained by differences in the biotic complexity of in vitro and natural environments(7,8). Specifically, by using the opportunistic pathogen Pseudomonas aeruginosa and its phage DMS3vir, we show that coexistence with other human pathogens amplifies the fitness trade-offs associated with the mutation of phage receptors, and therefore tips the balance in favour of the evolution of CRISPR-based resistance. We also demonstrate that this has important knock-on effects for the virulence of P. aeruginosa, which became attenuated only if the bacteria evolved surface-based resistance. Our data reveal that the biotic complexity of microbial communities in natural environments is an important driver of the evolution of CRISPR-Cas adaptive immunity, with key implications for bacterial fitness and virulence.