The obligate intracellular parasite Toxoplasma gondii, a member of the phylum Apicomplexa that includes Plasmodium spp., is one of the most widespread parasites and the causative agent of toxoplasmosis. Micronemal proteins (MICs) are released onto the parasite surface just before invasion of host cells and play important roles in host cell recognition, attachment and penetration. Here, we report the atomic structure for a key MIC, TgMIC1, and reveal a novel cell-binding motif called the microneme adhesive repeat (MAR). Using glycoarray analyses, we identified a novel interaction with sialylated oligosaccharides that resolves several prevailing misconceptions concerning TgMIC1. Structural studies of various complexes between TgMIC1 and sialylated oligosaccharides provide high-resolution insights into the recognition of sialylated oligosaccharides by a parasite surface protein. We observe that MAR domains exist in tandem repeats, which provide a highly specialized structure for glycan discrimination. Our work uncovers new features of parasite-receptor interactions at the early stages of host cell invasion, which will assist the design of new therapeutic strategies.