Based on evidence that it can reduce HIV transmission by up to 60%, male circumcision (MC) is being scaled up in high HIV prevalence settings. We present data from operations research into the introduction of MC in Zambia, assessing informed consent (IC) procedures for adolescent MC clients. We administered a comprehension test among adult (n = 311) and adolescent (n = 115) clients at 10 clinics around Lusaka between the counselling and IC process. We conducted semi-structured interviews with adolescent (13–17 years) MC clients 1 week post-surgery (n = 28) and 13 key informants (service providers and stakeholders). We conducted six focus group discussions (FGDs) among 36 parents/guardians; half who had chosen MC for their sons, half who had not. Data reveal complex interactions between adolescent and parent/guardian regarding making and authorizing the decision to circumcise. Although comprehension was generally high, adolescents scored significantly (p < 0.05) lower than adult clients on two questions, reflecting difficulty in understanding the key concepts associated with MC. Adolescent clients were significantly less likely than adult clients to report feeling comfortable with the decision to undergo MC (44% vs. 13%, p < 0.05). Qualitative data indicate that IC procedures for minors are poorly understood and inconsistently implemented at clinic sites, at a time when regulation was changing. The disparity between IC procedures for research and for surgery limits study findings; however, we underscore the absolute importance of creating an environment in which human rights abuses are prevented. We recommend that service providers take steps to strengthen the IC process for minors, including training providers and publicizing consent requirements in community outreach activities.