Local beliefs and practices about voluntary medical male circumcision (VMMC) may influence uptake and effectiveness. Data were gathered through interviews with 40 people from four ethnically mixed fishing communities in Uganda. Some men believed that wound healing could be promoted by contact with vaginal fluids while sex with non-regular partners could chase away spirits - practices which encouraged unsafe sexual practices. Information given by providers stressed that VMMC did not afford complete protection from sexually-transmitted infections, however, a number of male community members held the view that they were fully protected once circumcised. Both men and women said that VMMC was good not just for HIV prevention but also as a way of maintaining hygiene among the men. The implementation of VMMC in high-HIV prevalence settings needs to take account of local beliefs about circumcision, working with local religious/social group leaders, women and peers in the roll-out of the intervention.