When the rhizosphere is nitrogen-starved, legumes and rhizobia (soil bacteria) enter into a symbiosis that enables the fixation of atmospheric dinitrogen. This implies a complex chemical dialogue between partners and drastic changes on both plant roots and bacteria. Several recent works pointed out the importance of rhizobial surface polysaccharides in the establishing of the highly specific symbiosis between symbionts. Exopolysaccharides appear to be essential for the early infection process. Lipopolysaccharides exhibit specific roles in the later stages of the nodulation processes such as the penetration of the infection thread into the cortical cells or the setting up of the nitrogen-fixing phenotype. More generally, even if active at different steps of the establishing of the symbiosis, all the polysaccharide classes seem to be involved in complex processes of plant defense inhibition that allow plant root invasion. Their chemistry is important for structural recognition as well as for physico-chemical properties.