Classifying viruses systematically has remained a key challenge of virology due to the absence of universal genes and vast genetic diversity of viruses. In particular, the most dominant and diverse group of viruses, the tailed double-stranded DNA viruses of prokaryotes belonging to the class Caudoviricetes, lack sufficient similarity in the genetic machinery that unifies them to reconstruct an inclusive, stable phylogeny of these genes. While previous approaches to organize tailed phage diversity have managed to distinguish various taxonomic levels, these methods are limited in scalability, reproducibility, and the inclusion of modes of evolution, like gene gains and losses, remain key challenges. Here, we present a novel, comprehensive, and reproducible framework for examining evolutionary relationships of tailed phages. In this framework, we compare phage genomes based on the presence and absence of a fixed set of gene families which are used as binary trait data that is input into maximum likelihood models. Our resulting phylogeny stably recovers known taxonomic families of tailed phages, with and without the inclusion of metagenome-derived phages. We also quantify the mosaicism of replication and structural genes among known families, and our results suggest that these exchanges likely underpin the emergence of new families. Additionally, we apply this framework to large phages (>
100 kilobases) to map emergences of traits associated with genome expansion. Taken together, this evolutionary framework for charting and organizing tailed phage diversity improves the systemization of phage taxonomy, which can unify phage studies and advance our understanding of their evolution.