Critical to preventing the spread of HIV is promoting condom use among HIV-positive individuals. Previous studies suggest that gender norms (social and cultural constructions of the ways that women and men are expected to behave) may be an important determinant of condom use. However, the relationship has not been evaluated among HIV-positive women and men in South Africa. We examined gender norms and condom use at last sex among 550 partnerships reported by 530 sexually-active HIV-positive women (372) and men (158) who had sought care, but not yet initiated antiretroviral therapy in a high HIV-prevalence rural setting in KwaZulu-Natal, South Africa between January 2009 and March 2011. Participants enrolled in the cohort study completed a baseline questionnaire that detailed their socio-demographic characteristics, socio-economic circumstances, religion, HIV testing history and disclosure of HIV status, stigma, social capital, gender norms and self-efficacy. Gender norms did not statistically differ between women and men (p = 0.18). Overall, condoms were used at last sex in 58% of partnerships. Although participants disclosed their HIV status in 66% of the partnerships, 60% did not have knowledge of their partner's HIV status. In multivariable logistic regression, run separately for each sex, women younger than 26 years with more equitable gender norms were significantly more likely to have used a condom at last sex than those of the same age group with inequitable gender norms (OR = 8.88, 95% CI 2.95-26.75); the association between condom use and gender norms among women aged 26+ years and men of all ages was not statistically significant. Strategies to address gender inequity should be integrated into positive prevention interventions, particularly for younger women, and supported by efforts at a societal level to decrease gender inequality.