  The nuclear recoil correction to the bound-electron g factor in H-like atoms
is calculated to first order in $m/M$ and to all orders in $\alpha Z$. The
calculation is performed in the range Z=1-100. A large contribution of terms of
order $(\alpha Z)^5$ and higher is found. Even for hydrogen, the higher-order
correction exceeds the $(\alpha Z)^4$ term, while for uranium it is above the
leading $(\alpha Z)^2$ correction.
