Efficient infection of cells by human papillomaviruses (HPV) and pseudovirions requires primary interaction with cell surface proteoglycans, with apparent preference for species carrying heparan sulfate (HS) side chains. To identify residues contributing to virus/cell interaction, we performed point mutational analysis of the HPV16 major capsid protein, L1, targeting surface-exposed amino acid residues. Replacement of lysine residues 278, 356, or 361 for alanine reduced cell binding and infectivity of pseudovirions. Various combinations of these amino acid exchanges further decreased cell attachment and infectivity, with residual infectivity of less than 5% for the triple mutant, suggesting these lysine residues cooperate in HS binding. Single, double, or triple exchanges for arginine did not impair infectivity, demonstrating that interaction is dependent on charge distribution rather than sequence-specific. The lysine residues are located within a pocket on capsomere surface, which was previously proposed as putative receptor binding site. Fab fragments of binding-neutralizing antibody H16.56E that recognize an epitope directly adjacent to lysine residues strongly reduced HS-mediated cell binding, further corroborating our findings. In contrast, mutation of basic surface residues located in the cleft between capsomeres outside this pocket did not significantly reduce interaction with HS or resulted in assembly-deficient proteins. Computer-simulated heparin docking suggested that all three lysine residues can form hydrogen bonds with 2-O-, 6-O-, and N-sulfate groups of a single HS molecule with a minimal saccharide domain length of 8 monomer units. This prediction was experimentally confirmed in binding experiments using capsid protein and heparin molecules of defined length and sulfate group modifications.