Estimates of the onset of sediment motion are integral for flood protection and river management but are often highly inaccurate. The critical shear stress (τ*_c) for grain entrainment is often assumed constant, but measured values can vary by almost an order of magnitude between rivers. Such variations are typically explained by differences in measurement methodology, grain size distributions, or flow hydraulics, whereas grain resistance to motion is largely assumed to be constant. We demonstrate that grain resistance varies strongly with the bed structure, which is encapsulated by the particle height above surrounding sediment (protrusion, p) and intergranular friction (ϕ_f). We incorporate these parameters into a novel theory that correctly predicts resisting forces estimated in the laboratory, field, and a numerical model. Our theory challenges existing models, which significantly overestimate bed mobility. In our theory, small changes in p and ϕ_f can induce large changes in τ*_c without needing to invoke variations in measurement methods or grain size. A data compilation also reveals that scatter in empirical values of τ*_c can be partly explained by differences in p between rivers. Therefore, spatial and temporal variations in bed structure can partly explain the deviation of τ*_c from an assumed constant value. Given that bed structure is known to vary with applied shear stresses and upstream sediment supply, we conclude that a constant τ*_c is unlikely. Values of τ*_c are not interchangeable between streams, or even through time in a given stream, because they are encoded with the channel history.