The effect of different cooling temperatures and durations on resistance to freezing and to frozen storage at −20 °C in Lactobacillus acidophilus RD758 was studied, by using a central composite rotatable design. A cold adaptation was observed when the cells were maintained at moderate temperature (26 °C) for a long time (8 h) before being cooled to the final temperature of 15 °C. These conditions led to a low rate of loss in acidification activity during frozen storage (0.64 min day−1) and a high residual acidification activity after 180 days of frozen storage (1011 min). The experimental design allowed us to determine optimal cooling conditions, which were established at 28 °C during 8 h. Adaptation to cold temperatures was related to an increase in the unsaturated to saturated fatty acid ratio and in the relative cycC19:0 fatty acid concentration. Moreover, an increased synthesis of four specific proteins was observed as an adaptive response to the optimal cooling conditions. They included the stress protein ATP-dependent ClpP and two cold induced proteins: pyruvate kinase and a putative glycoprotein endopeptidase.