In efficacy trials male circumcision (MC) protected men against HIV infection. Planners need information relevant to MC programmes in practice. In 2008, we interviewed 2915 men and 4549 women aged 15-29 years in representative cluster samples in Botswana, Namibia and Swaziland, asking about socio-economic characteristics, knowledge and attitudes about HIV and MC and MC history. We tested finger prick blood samples for HIV. We calculated weighted frequencies of MC knowledge and attitudes, and MC history and HIV status. Multivariate analysis examined associations between MC and other variables and HIV status. In Botswana, 11% of young men reported MC, 28% in Namibia and 8% in Swaziland; mostly (75% in Botswana, 94% - mostly Herero - in Namibia and 68% in Swaziland) as infants or children. Overall, 6.5% were HIV positive (8.3% Botswana, 2.6% Namibia and 9.1% Swaziland). Taking other variables into account, circumcised men were as likely as uncircumcised men to be HIV positive. Nearly half of the uncircumcised young men planned to be circumcised; two-thirds of young men and women planned to have their sons circumcised. Some respondents had inaccurate beliefs and unhelpful views about MC and HIV, with variation between countries. Between 9 and 15% believed a circumcised man is fully protected against HIV; 20-26% believed men need not be tested for HIV before MC; 14-26% believed HIV-positive men who are circumcised cannot transmit the virus; and 8-34% thought it was "okay for a circumcised man to expect sex without a condom". Inaccurate perceptions about protection from MC could lead to risk compensation and reduce women's ability to negotiate safer sex. More efforts are needed to raise awareness about the limitations of MC protection, especially for women, and to study the interactions between MC roll out programmes and primary HIV prevention programmes.