Specific cleavage of proteins by proteases is essential for several cellular, physiological, and viral processes. Chymotrypsin-related proteases that form the PA clan in the MEROPS classification of proteases is one of the largest and most diverse group of proteases. The PA clan comprises serine proteases from bacteria, eukaryotes, archaea, and viruses and chymotrypsin-related cysteine proteases from positive-strand RNA viruses. Despite low amino acid sequence identity, all PA clan proteases share a conserved double β-barrel structure. Using an automated structure-based hierarchical clustering method, we identified a common structural core of 72 amino acid residues for 143 PA clan proteases that represent 12 protein families and 11 subfamilies. The identified core is located around the catalytic site between the two β-barrels and resembles the structures of the smallest PA clan proteases. We constructed a structure-based distance tree derived from the properties of the identified common core. Our structure-based analyses support the current classification of these proteases at the subfamily level and largely at the family level. Structural alignment and structure-based distance trees could thus be used for directing objective classification of PA clan proteases and to strengthen their higher order classification. Our results also indicate that the PA clan proteases of positive-strand RNA viruses are related to cellular heat-shock proteases, which suggests that the exchange of protease genes between viruses and cells might have occurred more than once.