Comparative interactomics is a strategy for inferring potential interactions among orthologous proteins or “iginterologs”. Herein we focus, in contrast to standard homology-based inference, on the divergence of protein interaction profiles among closely related organisms, showing that the approach can correlate specific traits to phenotypic differences. As a model, this new comparative interactomic approach was applied at a large scale to human papillomaviruses (HPVs) proteins. The oncogenic potential of HPVs is mainly determined by the E6 and E7 early proteins. We have mapped and overlapped the virus-host protein interaction networks of E6 and E7 proteins from 11 distinct HPV genotypes, selected for their different tropisms and pathologies. We generated robust and comprehensive datasets by combining two orthogonal protein interation assays: yeast two-hybrid (Y2H), and our recently described “High-Throughput Gaussia princeps Protein Complementation Assay” (HT-GPCA). HT-GPCA detects protein interaction by measuring the interaction-mediated reconstitution of activity of a split Gaussia princeps luciferase. Hierarchical clustering of interaction profiles recapitulated HPV phylogeny and was used to correlate specific virus-host interaction profiles with pathological traits, reflecting the distinct carcinogenic potentials of different HPVs. This comparative interactomics constitutes a reliable and powerful strategy to decipher molecular relationships in virtually any combination of microorganism-host interactions.