Lactic acid bacteria often suffer cold stress, especially when they are frozen for being stored as starters or in culture collections. Depending on the temperature level, cells answer to cold stress by passive and/or active responses, the latter helping them to counterbalance the negative effect of low temperatures. During freezing, cell deterioration or death occur as a consequence of four kinds of stress that trigger passive responses: Thermal stress induces phase transitions in membrane lipids and modification of membrane fluidity. Due to the formation of ice crystals, osmotic stress leads to a reduction of cellular volume, protein deterioration and changes in intracellular pH and mechanical stress causes destruction of membrane and cellular structures. Solute concentration enhances oxidative reactions of membrane lipids. When the cold stress is moderate, cells develop some active responses to better resist harsh conditions. By modifying their membrane fatty acid composition, they change their membrane fluidity to adapt to low temperatures. The transient induction of general or stress proteins is reported as a second mechanism. Some of these proteins act as molecular chaperones, which assist the cells for non-covalent folding and unfolding, and prevent proteins from taking conformations that would be inactive. These mechanisms combine to make the cells more cryotolerant.