The nuclear recoil effect on the g-factor of H- and Li-like heavy ions is evaluated to all orders in α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 ²⁰⁸Pb⁷⁹⁺ and ²³⁸U⁸⁹⁺ 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 gfactor 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 of the strong-coupling regime beyond the Furry picture.