Control of mRNA half-life is a powerful strategy to adjust individual mRNA levels to various stress conditions, because the mRNA degradation rate controls not only the steady-state mRNA level but also the transition speed of mRNA levels. Here, we analyzed mRNA half-life changes in response to cold stress in Arabidopsis cells using genome-wide analysis, in which mRNA half-life measurements and transcriptome analysis were combined. Half-lives of average transcripts were determined to be elongated under cold conditions. Taking this general shift into account, we identified more than a thousand transcripts that were classified as relatively stabilized or relatively destabilized. The relatively stabilized class was predominantly observed in functional categories that included various regulators involved in transcriptional, post-transcriptional and post-translational processes. On the other hand, the relatively destabilized class was enriched in categories related to stress and hormonal response proteins, supporting the idea that rapid decay of mRNA is advantageous for swift responses to stress. In addition, pentatricopeptide repeat, cyclin-like F-box and Myb transcription factor protein families were significantly over-represented in the relatively destabilized class. The global analysis presented here demonstrates not only the importance of mRNA turnover control in the cold stress response but also several structural characteristics that might be important in the control of mRNA stability.