Cryptosporidium parvum is an apicomplexan parasite that can cause serious watery diarrhea, cryptosporidiosis, in human and other mammals. C. parvum invades gastrointestinal epithelial cells, which have abundant glycosaminoglycans on their cell surface. However, little is known about the interaction between C. parvum and glycosaminoglycans. In this study, we assessed the inhibitory effect of sulfated polysaccharides on C. parvum invasion of host cells and identified the parasite ligands that interact with sulfated polysaccharides. Among five sulfated polysaccharides tested, heparin had the highest, dose-dependent inhibitory effect on parasite invasion. Heparan sulfate-deficient cells were less susceptible to C. parvum infection. We further identified 31 parasite proteins that potentially interact with heparin. Of these, we confirmed that C. parvum elongation factor 1α (CpEF1α), which plays a role in C. parvum invasion, binds to heparin and to the surface of HCT-8 cells. Our results further our understanding of the molecular basis of C. parvum infection and will facilitate the development of anti-cryptosporidial agents.