Genital human papillomaviruses (HPV) represent the most common sexually transmitted agents and are classified into low or high risk by their propensity to cause genital warts or cervical cancer, respectively. Topical microbicides against HPV may be a useful adjunct to the newly licensed HPV vaccine. A main objective in the development of novel microbicides is to block HPV entry into epithelial cells through cell surface heparan sulfate proteoglycans. In this study, selective chemical modification of the Escherichia coli K5 capsular polysaccharide was integrated with innovative biochemical and biological assays to prepare a collection of sulfated K5 derivatives with a backbone structure resembling the heparin/heparan biosynthetic precursor and to test them for their anti-HPV activity. Surface plasmon resonance assays revealed that O-sulfated K5 with a high degree of sulfation [K5-OS(H)] and N,O-sulfated K5 with a high [K5-N,OS(H)] or low [K5-N,OS(L)] sulfation degree, but not unmodified K5, N-sulfated K5, and O-sulfated K5 with low levels of sulfation, prevented the interaction between HPV-16 pseudovirions and immobilized heparin. In cell-based assays, K5-OS(H), K5-N,OS(H), and K5-N,OS(L) inhibited HPV-16, HPV-18, and HPV-6 pseudovirion infection. Their 50% inhibitory concentration was between 0.1 and 0.9 mug/ml, without evidence of cytotoxicity. These findings provide insights into the design of novel, safe, and broad-spectrum microbicides against genital HPV infections.