Malaria during pregnancy remains a major health problem in Plasmodium falciparum endemic areas. Parasite-infected red blood cells sequester in the placenta through interaction between parasite-expressed protein VAR2CSA and the glycosaminoglycan chondroitin sulfate A (CS) abundantly present in the intervillous space. Placental malaria can have severe consequences for both mother and child by causing maternal anemia, low birth weight and stillbirth. Several VAR2CSA-based vaccines have been developed and clinically tested but they have failed to induce an antibody response that effectively inhibits placental adhesion of different genetic variants of VAR2CSA. The interaction between VAR2CSA and CS represents a unique case of an evolution-driven high-affinity interaction between a protein and an oncofetal carbohydrate. Here, we report cryo-EM structures of the VAR2CSA ectodomain up to 3.1 Å resolution revealing an overall V-shaped architecture and a complex domain organization. Notably, the surface displays a single significantly electropositive patch, compatible with binding of negatively charged CS. Using molecular docking and molecular dynamics simulations as well as comparative hydroxyl radical protein foot-printing of VAR2CSA in complex with placental CS, we identify the CS-binding groove, intersecting with the positively charged patch of the central VAR2CSA structure. We identify distinctive conserved structural features upholding the macro-molecular domain complex and CS binding capacity of VAR2CSA as well as divergent elements possibly allowing immune escape at or near the CS binding site. These observations enable rational design of second-generation placental malaria vaccines eliciting broadly VAR2CSA-reactive antibodies and novel cancer therapies.