Using the 2005–2006 Zimbabwe Demographic and Health Survey, we investigated the prevalence of HIV testing uptake within a sample of women (6839) and men (5315), and identified the independent effects of AIDS stigma on testing uptake, with particular emphasis on three pathways to testing: voluntary testing, testing when offered, and testing when required. The prevalence of self-reported HIV testing was higher among women (31%) than men (22%). For women, the main pathway to testing uptake was to accept testing when it is offered (46%), whereas for men it was voluntary testing (53%). In the logistic regression models, we found that social rejection stigma was inversely associated with uptake across all pathways of testing for women, but not men. As regards observed enacted stigma, respondents who both knew someone with HIV and had observed discrimination against someone with HIV were more likely to test for HIV through all pathways, while those who knew someone with HIV but had not observed stigma were more likely to test voluntarily. Individual characteristics important to the adoption of testing included high educational attainment, religion, exposure to mass media, and ever use of condoms; while being never married and self-perceived risk were barriers to testing. Programmatic strategies aimed at increasing HIV testing uptake should consider reducing stigma toward people living with HIV/AIDS and also addressing the role of agency and structure in individual's decision to be tested for HIV.