When voluntary medical male circumcision (MC) was confirmed as an effective tool for HIV prevention in sub-Saharan Africa in 2007, many public health policy makers and practitioners were eager to implement the intervention. How to roll out the tool as part of comprehensive strategy however was less clear. At the time, very little was known about the capacity of health systems to scale delivery of the new intervention. Today, nearly all countries prioritized for the intervention are far behind their targets. To contribute to the discourse on why this is, we develop a historical analysis of medical MC planning in sub-Saharan Africa using our own experience of this process in Rwanda. We compare our previously unpublished feasibility analysis from 2008 with international research published in 2009, which suggested how Rwanda could reduce HIV incidence through a rapid MC intervention, and Rwanda’s eventual 2010 official operational plan. We trace how, in the face of uncertainty, operational plans avoided discussing the details of feasibility and focused instead on defining optimal circumcision capacity needed to achieve country level target reductions in HIV incidence. We show a distinct gap between the targets set in the official operational plan and what we determined was feasible in 2008. With actual data from the ground now available, we show our old feasibility models more closely approximate circumcision delivery rates to date. With an eye toward the future of long-term policy planning, we discuss the mechanics of how accountability gaps like this occur in global health policy making and how practitioners can better create achievable operational targets.