Despite efforts to broaden participation in computer science and its related fields, there exist stark disparities in participation in computer related fields by gender, race/ethnicity, and socio-economic status. One approach to combat these disparities is to expose children to computing concepts early, to provide them with the foundational skills needed to be successful in later computing courses. This article reports on the results of a randomized controlled trial evaluation of a novel curriculum that teaches computational thinking skills to children ages three through five in Head Start classrooms. We find that the curriculum improved child performance on a validated computational thinking assessment by a significant 0.66 standard deviations (SDs), equivalent to moving the median control group student to the 75th percentile had they been exposed to the curriculum. Effects of similar magnitude were seen for most domains of the computational thinking assessment and subgroups of students. In a subset of students for whom we were able to obtain teacher ratings on formative assessments used in Head Start, we saw the curriculum improved teacher ratings of math development by a significant 0.36 SDs but it had no effect on teacher ratings of literacy or social-emotional development. Though we were underpowered to detect effects on teacher outcomes, teacher survey results indicate that the curriculum may improve teacher confidence and knowledge in teacher computational thinking skills, especially for novice and assistant teachers. These results indicate that prekindergarten can be an opportune time to start addressing disparities by teaching foundational computing skills.