Variations of carcinogenicity of human papillomaviruses are related to variations of the E6 and E7 interactome. While different HPV species and genera are known to target distinct host proteins, the fine differences between E6 and E7 of closely related HPVs, supposed to target the same cellular protein pools, remain to be addressed. We compare the oncogenic E6 proteins of the closely related high-risk HPV31 and HPV16 with regard to their structure and their efficiency of ternary complex formation with their cellular targets p53 and E6AP, which results in p53 degradation. We solved the crystal structure of 31 E6 bound to the E6AP LxxLL motif. HPV16 E6 and 31 E6 structures are highly similar, but a few sequence variations lead to different protein contacts within the ternary complex and, as quantified here, an overall lower binding affinity of 31 E6 than 16 E6. These results align with the observed lower p53 degradation potential of 31 E6.