BACKGROUND: Despite the importance of male circumcision (MC) prevalence to HIV prevention efforts in Eastern and Southern Africa, there has been no systematic analysis on the correlates of male circumcision. This analysis identifies correlates of MC in 12 countries in the region with available data. METHODS: Data from the male questionnaire of DHS surveys collected between 2006-2011 in Ethiopia, Kenya, Lesotho, Malawi, Mozambique, Namibia, Rwanda, Swaziland, Tanzania, Uganda, Zambia, and Zimbabwe were analyzed. The dependent variable was self-reported male circumcision status. Independent variables included age, education, wealth quintile, place of residence, ethnicity, religion and region. Bivariate and multivariate analyses were conducted separately for each country. RESULTS: MC prevalence ranged from 8.2 percent in Swaziland to 92.2 percent in Ethiopia. Bivariate analyses showed a consistent positive association between age (being older) and male circumcision. Education, wealth quintile, and place of residence were either not significantly related or differed in the direction of the relationship by country. Multivariate logistic regression showed three variables consistently associated with MC status: age (being older), religion (being Muslim) and ethnicity. DISCUSSION: These data were collected prior to the scale-up of voluntary medical male circumcision (VMMC) programs in 11 of the 12 countries. As the VMMC scale-up intensifies in countries across Eastern and Southern Africa, the correlates of VMMC are likely to change, with (younger) age and education emerging as key correlates of VMMC performed in medical settings. The centuries-long tradition among Muslims to circumcise should continue to favor MC among this group. Non-circumcising ethnicities may become more open to MC if promoted as a health practice for decreasing HIV risk.