Bacterial pathogens commonly carry prophages that express virulence factors, and human strains of Staphylococcus aureus carry Sa3int phages, which promote immune evasion. Recently, however, these phages have been found in livestock-associated, methicillin-resistant S. aureus (LA-MRSA). This is surprising, as LA-MRSA strains contain a mutated primary bacterial integration site, which likely explains why the rare integration events that do occur mostly happen at alternative locations. Using deep sequencing, we show that after initial integration at secondary sites, Sa3int phages adapt through nucleotide changes in their attachment sequences to increase homology with alternative bacterial attachment sites. Importantly, this homology significantly enhances integrations in new rounds of infections. We propose that promiscuity of the phageencoded tyrosine recombinase is responsible for establishment of Sa3int phages in LAMRSA. Our results demonstrate that phages can adopt extensive population heterogeneity, leading to establishment in strains lacking bona fide integration sites. Ultimately, their presence may increase virulence and zoonotic potential of pathogens with major implications for human health.