Background: The effects of increases in physical activity (PA) on early literacy skills in preschool children are not known. Methods: Fifty-four African-American preschool children from a low socioeconomic urban Head Start participated over 8 months. A 2-group, quasi-experimental design was used with one preschool site participating in the PA intervention and a second site participating as the control site. The PA program was designed to promote 300 minutes/week of moderate to vigorous PA academic lessons. Academic achievement related to early literacy and phonological awareness in the areas of rhyming and alliteration were assessed at baseline, 4 and 8 months. Results: Over 8 months, rhyming significantly (p < 0.01) improved in the PA group (173 ± 12%) compared with the controls (28 ± 8%) resulting in between group differences at 8 months (p < 0.01). Alliteration significantly (p < 0.01) improved in the PA group (52 ± 16%) compared with controls (13 ± 5%), resulting in between group differences at 8 months (p < 0.01). As minutes of exposure to moderate to vigorous PA increased, the change in picture naming (R[superscript 2] = 0.35, p < 0.05), alliteration (R[superscript 2] = 0.38, p < 0.05), and rhyming (R[superscript 2] = 0.42, p < 0.05), increased. Conclusion: A teacher-directed PA program is effective at increasing PA and improving early literacy.