Life has effectively colonized most of our planet and extremophilic organisms require specialized enzymes to survive under harsh conditions. Cold-loving organisms (psychrophiles) express heat-labile enzymes that possess a high specific activity and catalytic efficiency at low temperatures. A remarkable universal characteristic of cold-active enzymes is that they show a reduction both in activation enthalpy and entropy, compared to mesophilic orthologs, which makes their reaction rates less sensitive to falling temperature. Despite significant efforts since the early 1970s, the important question of the origin of this effect still largely remains unanswered. Here we use cold- and warm-active trypsins as model systems to investigate the temperature dependence of the reaction rates with extensive molecular dynamics free energy simulations. The calculations quantitatively reproduce the catalytic rates of the two enzymes and further yield high-precision Arrhenius plots, which show the characteristic trends in activation enthalpy and entropy. Detailed structural analysis indicates that the relationship between these parameters and the 3D structure is reflected by significantly different internal protein energy changes during the reaction. The origin of this effect is not localized to the active site, but is found in the outer regions of the protein, where the cold-active enzyme has a higher degree of softness. Several structural mechanisms for softening the protein surface are identified, together with key mutations responsible for this effect. Our simulations further show that single point-mutations can significantly affect the thermodynamic activation parameters, indicating how these can be optimized by evolution. 