Age at first reproduction is an important determinant of individual variation in reproductive success in ungulates, but few studies have examined its relationship with later fitness-related traits in males. We used a long-term individual based study of a harvested moose population to quantify the individual reproductive performance and survival of males, as well as to examine the determinants of age at first reproduction and consequences of age at first reproduction on lifetime breeding success. The probability that a male successfully reproduced at the age of two was negatively related to the mean age of adult males in the population, but the relationship weakened with increasing population size. Large antlers and large body mass relative to other males in the population increased the number of calves sired at their first successful mating season. In addition, those that successfully reproduced as two year-olds were more likely to sire calves the next year, making them more productive at a given age compared to those that first reproduced at the age of three or older. We emphasize the importance for males to start reproducing as soon as possible in a harvested population to gain lifetime fitness benefits, as surviving the hunt is a major determinant of reproductive success in this population. We found no costs of early reproduction in males, hence leading to high individual heterogeneity in male reproductive performance. The apparent lack of reproductive costs could partly be explained by the age distribution in the population, individual variation in early-life body mass and antler size, and differences in probabilities of being killed during hunt between successful and unsuccessful males.