ABSTRACT Human mastadenovirus D (HAdV-D) is exceptionally rich in type among the seven human adenovirus species. This feature is attributed to frequent intertypic recombination events that have reshuffled orthologous genomic regions between different HAdV-D types. However, this trend appears to be paradoxical, as it has been demonstrated that the replacement of some of the interacting proteins for a specific function with other orthologues causes malfunction, indicating that intertypic recombination events may be deleterious. In order to understand why the paradoxical trend has been possible in HAdV-D evolution, we conducted an interregional coevolution analysis between different genomic regions of 45 different HAdV-D types and found that ca. 70% of the genome has coevolved, even though these are fragmented into several pieces via short intertypic recombination hot spot regions. Since it is statistically and biologically unlikely that all of the coevolving fragments have synchronously recombined between different genomes, it is probable that these regions have stayed in their original genomes during evolution as a platform for frequent intertypic recombination events in limited regions. It is also unlikely that the same genomic regions have remained almost untouched during frequent recombination events, independently, in all different types, by chance. In addition, the coevolving regions contain the coding regions of physically interacting proteins for important functions. Therefore, the coevolution of these regions should be attributed at least in part to natural selection due to common biological constraints operating on all types, including protein-protein interactions for essential functions. Our results predict additional unknown protein interactions. IMPORTANCE Human mastadenovirus D , an exceptionally type-rich human adenovirus species and causative agent of different diseases in a wide variety of tissues, including that of ocular region and digestive tract, as well as an opportunistic infection in immunocompromised patients, is known to have highly diverged through frequent intertypic recombination events; however, it has also been demonstrated that the replacement of a component protein of a multiprotein system with a homologous protein causes malfunction. The present study solved this apparent paradox by looking at which genomic parts have coevolved using a newly developed method. The results revealed that intertypic recombination events have occurred in limited genomic regions and been avoided in the genomic regions encoding proteins that physically interact for a given function. This approach detects purifying selection against recombination events causing the replacement of partial components of multiprotein systems and therefore predicts physical and functional interactions between different proteins and/or genomic elements.