OBJECTIVES: To identify factors associated with sexual debut and early age at first sex (AFS) among young men and women (12-25 years) in a population with a high prevalence and incidence of HIV in rural South Africa. METHODS: Longitudinal data from four rounds (2003-7) of a prospective population-based HIV and sexual behaviour survey in rural KwaZulu-Natal were used to investigate the distribution and predictors of earlier first sex. Survival analyses were used, and each analysis considered men and women separately. RESULTS: Among the 4724 women and 4029 men who were virgins at the beginning of the period, the median AFS was 18.5 and 19.2 years, respectively. In multivariable models, factors associated with earlier AFS across gender were periurban residence (vs rural), ever use of alcohol and knowing at least one person who had HIV, while school attendance had a significant protective effect. Other factors were important for one gender only. Maternal death was significantly associated with earlier AFS for women, in the same way that paternal death was for young men, while mother's membership of the same household significantly delayed AFS of young men. The analysis of early first sex confirmed the same factors to be important as in the overall analyses for men and women. CONCLUSION: Given the association of individual, household and community level factors with sexual debut, a multisectorial approach to prevention and targeting in youth programmes is recommended.