From 2000 to 2010, Rwanda implemented comprehensive health sector reforms to strengthen the public health system, with the aim of reducing maternal and newborn deaths in line with Millennium Development Goal 5, among many other improvements in national health. Based on a systematic review of the literature, national policy documents and three Demographic & Health Surveys (2000, 2005 and 2010), this paper describes the reforms and the policies they were based on, and provides data on the extent of Rwanda’s progress in expanding the coverage of four key women’s health services. Progress took place in 2000–2005 and became more rapid after 2006, mostly in rural areas, when the national facility-based childbirth policy, performance-based financing, and community-based health insurance were scaled up. Between 2006 and 2010, the following increases in coverage took place as compared to 2000–2005, particularly in rural areas, where most poor women live: births with skilled attendance (77% increase vs. 26%), institutional delivery (146% increase vs. 8%), and contraceptive prevalence (351% increase vs. 150%). The primary factors in these improvements were increases in the health workforce and their skills, performance-based financing, community-based health insurance, and better leadership and governance. Further research is needed to determine the impact of these changes on health outcomes in women and children.