The quantum electrodynamic theory of the nuclear recoil effect on the atomic g factor to all orders in [Formula Presented] and to first order in [Formula Presented] is formulated. The complete [Formula Presented]-dependence formula for the recoil correction to the bound-electron g factor in a hydrogenlike atom is derived. This formula is used to calculate the recoil correction to the bound-electron g factor in the order [Formula Presented] for an arbitrary state of a hydrogenlike atom.