HNBR was analyzed following low temperature storage (between 0 °C and −50 °C) in order to measure the effects of cold crystallization during exposure close to, and below, the glass transition temperature (Tg). Differential scanning calorimetry (DSC), dynamic mechanical thermal analysis (DMTA) and hardness testing were performed to measure the changes in melting enthalpy, shear stiffness and hardness as a result of low temperature exposure. An increase in crystallinity was measured even when the HNBR was held well below the Tg of the HNBR. Although the degree of crystallinity due to low temperature exposure is estimated to be quite small, a significant increase in hardness was seen after 24 h exposure. The changes in properties due to the presence of “microcrystalline” regions are especially relevant for permanently low temperature applications, since the material properties over longer timescales at low temperatures may deviate significantly from the material properties measured immediately after cooling.