Many studies ask whether older males are better at acquiring mates. Even so, how age affects reproductive success is still poorly understood because male age and mating history are confounded in most studies: older males usually have more mating experience. To what extent does mating history rather than age explain variation in male mating success? And how do mating history and male age determine paternity when there is also post-copulatory sexual selection? Here we experimentally manipulated the mating history of old and young males in the eastern mosquitofish (Gambusia holbrooki). We then recorded male mating behaviour and share of paternity (1259 offspring from 232 potential sires) when they competed for mates and fertilizations. Old males, and males with no mating experience, spent significantly more time approaching females, and attempting to mate, than did young males and those with greater mating experience. Male age and mating history interacted to affect paternity: old males benefited from having previous mating experience, but young males did not. Our results highlight that the age-related changes in male reproductive traits and in paternity that have been described in many taxa, may be partly attributable to male mating history and not simply to age itself.