High risk human papillomavirus types 16 (HPV16) and 18 (HPV18) can cause cervical cancer. Efficient infection by HPV16 and HPV18 pseudovirions requires interactions of particles with cell-surface receptor heparan sulfate oligosaccharide. To understand the virus-receptor interactions for HPV infection, we determined the crystal structures of HPV16 and HPV18 capsids bound to the oligosaccharide receptor fragment using oligomeric heparin. The HPV-heparin structures revealed multiple binding sites for the highly negatively charged oligosaccharide fragment on the capsid surface, which is different from previously reported virus-receptor interactions in which a single type of binding pocket is present for a particular receptor. We performed structure-guided mutagenesis to generate mutant viruses, and cell binding and infectivity assays demonstrated the functional role of viral residues involved in heparin binding. These results provide a basis for understanding virus-heparan sulfate receptor interactions critical for HPV infection and for the potential development of inhibitors against HPV infection.