  The nuclear recoil effect on the $g$ factor of H- and Li-like heavy ions is
evaluated to all orders in $\alpha Z$. The calculations include an approximate
treatment of the nuclear size and the electron-electron interaction corrections
to the recoil effect. As the result, the second largest contribution to the
theoretical uncertainty of the $g$-factor values of $^{208}$Pb$^{79+}$ and
$^{238}$U$^{89+}$ is strongly reduced. Special attention is paid to tests of
the QED recoil effect on the $g$ factor in experiments with heavy ions. It is
found that, while the QED recoil effect on the $g$-factor value is masked by
the uncertainties of the nuclear size and nuclear polarization contributions,
it can be probed on a few-percent level in the specific difference of the $g$
factors of H- and Li-like heavy ions. This provides a unique opportunity to
test QED in a new region --- strong-coupling regime beyond the Furry picture.
