A lek is an aggregated male display that females attend for the purpose of fertilization. A male needs to climb the relative hierarchy to be available for mating when the peak of female estrus occurs. We analyzed the link between timing of lek use by males in relation to age, phenotype, territoriality, and mating success. For more than a decade, we collected radio-tracking data and behavioral observations of a lekking mammal, the fallow deer (Dama dama). Competitively stronger males (i.e., older and heavier males with larger antlers) moved to the lek before less competitive ones. However, an early arrival did not guarantee the territory defense for a longer period nor higher mating success. The early arrival seemed to be a necessary but not sufficient condition to be a successful male in a lek. In fact, the ability to defend a territory for longer was related to age, body mass, antler length but not arrival time. We accordingly argue that males move to the lek early because they need to engage in male–male interactions and scent-marking activities. Successful males left the lek later than unsuccessful ones. The latter did not attempt to compensate for their low mating success by remaining in the lek, likely adopting alternative strategies outside of it. Adult males seeking for a chance to defend the territory and mate have to move to the lek early and stay there until the end of the rut, though this does not guarantee them a higher mating success.