Viral taxonomy remains one of the most challenging frontiers in biology. Unlike cellular organisms, viruses lack universally conserved marker genes, while extensive horizontal gene transfer and genomic mosaicism obscure evolutionary relationships and limit sequence-based classification. This challenge is particularly evident in Caudoviricetes, where many species remain unassigned to higher taxonomic ranks within the current ICTV classification. We developed PhagePleats, a structure-based framework for bacteriophage classification that exploits whole-proteome structural similarity to infer evolutionary relationships beyond the limits of sequence conservation. Protein structures were predicted for 445,151 proteins from 4,082 representative Caudoviricetes genomes using ESMFold and clustered with Foldseek to generate genome-wide structural profiles. Phylogenetic relationships reconstructed from these profiles produced a revised taxonomic framework comprising 159 orders, 267 families, 502 subfamilies, and 1,189 genera. PhagePleats also enables rapid taxonomic classification of newly sequenced bacteriophage genomes by comparing their structural repertoires to this reference framework. These findings demonstrate that protein structure provides a powerful complementary framework for resolving deep viral evolutionary relationships and improving bacteriophage taxonomy.