Numerous observational studies and three clinical trials have shown male circumcision (MC) to be partially protective against HIV acquisition in heterosexual men. This has led to consideration of introducing circumcision as an HIV prevention strategy in parts of sub-Saharan Africa. This study assesses the acceptability of male circumcision as an intervention to improve male genital hygiene and reduce sexually transmitted infections, including HIV-1 in Zambia. Thirty-four focus group discussions were conducted - 17 with men and 17 with women - in four districts chosen to represent urban and rural communities where circumcision is and is not traditionally practiced. In communities where circumcision is little practiced, the main facilitators for acceptance were improved genital hygiene, HIV/STI prevention, and low cost. The main barriers were cultural tradition, high cost, pain, and concerns for safety. If MC is proven to reduce risk for HIV and STIs, most participants reported that they would seek circumcision for themselves or their partners or their sons if it was free or at a minimal cost. Acceptability of male circumcision for STI and HIV prevention appears to be high in Zambia.