There is considerable interest in the use of psychrotrophic bacteria for food biopreservation and in the understanding of cold adaptation mechanisms. The psychrotrophic biopreservative Lactococcus piscium strain CNCM I-4031 was studied for its growth behavior and proteomic responses after cold shock and during cold acclimation. Growth kinetics highlighted the absence of growth latency after cold shock, suggesting a very high promptness in cold adaptation, a behavior that has never been described before for lactic acid bacteria (LAB). A comparative proteomic analysis was applied with two-dimensional gel electrophoresis (2-DE), and upregulated proteins were identified by liquid chromatography-tandem mass spectrometry (LC-MS/MS). Both cold shock and cold acclimation triggered the upregulation of proteins involved in general and oxidative stress responses and fatty acid and energetic metabolism. However, 2-DE profiles and upregulated proteins were different under both conditions, suggesting a sequence of steps in cold adaptation. In addition, the major 7-kDa Csp protein was identified in the L. piscium CNCM I-4031 genome but was not cold regulated. The implication of the identified cold shock proteins and cold acclimation proteins in efficient cold adaptation, the possible regulation of a histidyl phosphocarrier protein, and the roles of a constitutive major 7-kDa Csp are discussed.