This paper presents the experiences and lessons learnt during the design and implementation of the randomized impact evaluation (IE) of a reading to learn (RtL) intervention in early primary grades. The study was to assess the impact of RtL on literacy and numeracy among pupils in low-performing districts in East Africa. The intervention was designed in a way that in each country one district implemented an intervention package that included teacher training, and teaching and learning materials; while the other district implemented this same package with an additional parental involvement component. Baseline data were collected in mid-2009 in Grades 1 and 2, and in 2010 for the incoming Grade 1. The endline data were collected in mid-2011. A total of 119 treatments and 110 control schools participated in the study. The randomized design provided an opportunity to attribute causality and also qualitatively establish pathways through which the intervention impacted on learning. The paper provides lessons learnt and demonstrates how the challenges faced during the evaluation were addressed. Additionally, the paper shows how IE was utilized to provide robust evidence of what works thus enabling policy-makers to make decisions on sustainability and scale-up of education interventions.