The effect of surface stress on the stiffness of cantilever beams remains an outstanding problem in the physical sciences. While numerous experimental studies report significant stiffness change due to surface stress, theoretical predictions are unable to rigorously and quantitatively reconcile these observations. In this Letter, we present the first controlled measurements of stress-induced change in cantilever stiffness with commensurate theoretical quantification. Simultaneous measurements are also performed on equivalent clamped-clamped beams. All experimental results are quantitatively and accurately predicted using elasticity theory. We also present conclusive experimental evidence for invalidity of the long-standing and unphysical axial force model, which has been widely applied to interpret measurements using cantilever beams. Our findings will be of value in the development of micro- and nanoscale resonant mechanical sensors.