Adenoviruses bind to a variety of human cells to cause infection. Both the B2 adenovirus 11 and B1 adenovirus 21 use protein knobs to bind to complement regulator CD46(SCR1-2) in order to gain entry into host cells. In each complex, the two proteins are highly negatively charged but bind to each other at an interface with oppositely charged surface patches. We computationally generated single-alanine mutants of charged residues in the complexes CD46(SCR1-2)-Ad11k and CD46(SCR1-2)-Ad21k. We used electrostatic clustering and Poisson-Boltzmann free energy calculations to propose a hypothesis on the role of electrostatics in association. Our results delineate specific interfacial electrostatic interactions that are critical for association in both CD46(SCR1-2)-Ad11k and CD46(SCR1-2)-Ad21k. These results will serve as a predictive tool in the selection of mutants with desired binding affinity in experimental mutagenesis studies. This study will also serve as a foundation for the design of inhibitors to treat adenovirus infections.