Cold acclimation (CA) leads to increased plant freezing tolerance during exposure to low, non-freezing temperatures as a result of many physiological, biochemical and molecular changes that have been extensively investigated. In addition, many plant species, such as Arabidopsis thaliana, respond to a subsequent exposure to mild, non-damaging freezing temperatures with an additional increase in freezing tolerance referred to as sub-zero acclimation (SZA). There is comparatively little information available about the molecular basis of SZA. However, previous transcriptomic studies indicated that cell wall modification may play an important role during SZA. Here we show that CA and SZA are accompanied by extensive changes in cell wall amount, composition and structure. While CA leads to a significant increase in cell wall amount, the relative proportions of pectin, hemicellulose and cellulose remained unaltered during both CA and SZA. However, both treatments resulted in more subtle changes in structure as determined by infrared spectroscopy and monosaccharide composition as determined by gas chromatography-mass spectrometry. These differences could be related through a proteomic approach to the accumulation of cell wall modifying enzymes such as pectin methylesterases, pectin methylesterase inhibitors and xyloglucan endotransglucosylases/hydrolases in the extracellular matrix.