BACKGROUND: Young people in South Africa are at high risk of HIV infection and yet may have more limited access to prevention and treatment services than others in the population. Testing facilitates the sharing of prevention messages but also enables the linkage to care and treatment of those who test positive and therefore has wider public health implications. METHODS: This baseline survey conducted in 2005 for a community randomized trial in rural KwaZulu-Natal explored factors associated with a history of ever, repeat and recent testing amongst sexually debuted men and women aged 18 to 32 years. RESULTS: Over 35% of this rural population ever tested for HIV, with men less likely to ever (unadjusted OR 0.26, 95% CI: 0.21-0.32) and repeatedly test than women (adjusted OR (aOR) 0.68, 95% CI: 0.48-0.97). Men aged 24-28 years (aOR 2.02, 95% CI: 1.10-3.71) and 29-32 years (aOR 2.69, 95% CI: 1.46-4.94) were more likely to ever test than those <20 years. Those who reported having discussed HIV with others had significantly greater odds of reporting ever (men's aOR 2.83, 95% CI: 1.63-4.89; women's aOR 3.36, 95% CI: 2.50-4.53), recent (irrespective of sex, aOR 2.87, 95% CI: 2.02-4.09) and repeat testing (aOR 2.02, 95% CI: 1.28-3.19). CONCLUSION: These findings highlight the need for novel youth- and men-friendly testing services and emphasises the importance of discussions about HIV in the home and community to encourage testing.