Over the last two decades, we have routinely published phylogenies describing the evolution of organisms and viruses using protein structure information. The structure-based trees offer several advantages over traditional approaches, including improved resolution of basal branches of the trees, a more realistic representation of evolutionary events such as gene duplication, loss, gain, and horizontal gene transfer, better handling of fast-evolving (micro)-organisms and organisms with parasitic tendencies (viruses), and reduced susceptibility to artifacts arising from sequence alignment and reconstruction in complex genomic datasets. Here, we present a generic protocol for phylogenomic analysis of molecular structure, which is timely considering the recent revolution in AI-driven models of protein structure prediction. While the protocol is illustrated with viral protein structures, the procedure is generic in nature and can be easily adapted for other structures (e.g., RNA) and molecular characteristics (e.g., molecular functions, pathways), thereby enriching the phylogenetic toolkit available to molecular biologists.