BACKGROUND In 2007, the World Health Organization endorsed male circumcision as an effective HIV prevention strategy. In 2008, the Government of Kenya (GoK) launched the national voluntary medical male circumcision (VMMC) program in Nyanza Province, the geographic home to the Luo, the largest non-circumcising ethnic group in Kenya. Currently, several other African countries are in the early stages of implementing this intervention. RESULTS This paper uses data from a health facility needs assessment (n = 81 facilities) and a study to evaluate the implementation of VMMC services in 16 GoK facilities (n = 2,675 VMMC clients) to describe Kenya's experience in implementing the national program. The needs assessment revealed that no health facility was prepared to offer the minimum package of services as outlined by the national guidelines, and partner organizations were called upon to fill this gap. The findings concerning human resource shortages facilitated the GoK's decision to endorse trained nurses to provide VMMCs, enabling more facilities to offer the service. Findings from the evaluation study resulted in replacing voluntary counseling and testing (VCT) with provider-initiated testing and counseling (PITC) and subsequently doubling the proportion of VMMC clients tested for HIV. CONCLUSIONS This paper outlines how certain challenges, like human resource shortages and low HIV test rates, were addressed through national policy changes, while other challenges, like large fluctuations in demand, were addressed locally. Currently, the program requires significant support from partner organizations, but a strategic plan is under development to continue to build capacity in GoK staff and facilities. Coordination between all parties was essential and was facilitated through the formation of national, provincial, and district VMMC task forces. The lessons learned from Kenya's VMMC implementation experience are likely generalizable to other African countries.