Genes encoding for virulence factors are frequently found on prophages, yet the evolutionary forces driving this association remain unclear. The evolutionary association of mobile elements with host-beneficial genes is known to be hindered by the stability of chromosomal loci and competition with mobile elements lacking accessory genes. Using a mathematical model that incorporates these constraints, we identify two key mechanisms that help overcome these barriers, resulting in the evolutionary linkage of accessory genes, like virulence genes, to prophages. First, we show that migration in between bacterial populations favours this linkage when the gene is beneficial in an environment where prophage induction is also upregulated. Second, we show that within-population spatial dynamics also promotes the association of weakly selected genes and phages. Here, virion dispersal allows phage-encoded genes to spread into patches of bacteria lacking the gene, giving them a selective advantage over immobile chromosomal genes. While both of these mechanisms are evidently applicable to phages, this is less clear for plasmids and other mobile elements. This helps to resolve the long-standing question of why phages, rather than other mobile genetic elements, appear to frequently carry virulence genes as cargo. By demonstrating how spatial heterogeneity and phage lifecycle dynamics drive gene association, our work provides new insights into the evolution of phage-encoded pathogenicity and bacterial adaptation.