Little is known about the dose–response of physical education interventions on motor coordination in preschoolers. Our aim was to investigate whether the development of motor skills changed depending on different amounts of a physical education program (PEP) in children aged 3–5 years. One hundred forty-five children were recruited from kindergartens and randomly divided into a control group (CG, n = 28), which did not perform any PEP, and two intervention groups, which performed 4 h/week (I1, n = 78) and 10 h/week (I2, n = 39) of a PEP for 16 weeks. Each lesson was set in the form of a programmed game in order to produce fun, thus increasing enthusiasm for participation. Before and after the intervention, locomotor and object control skills and the gross motor development quotient were assessed with the Italian version of the gross motor development test. Both intervention groups showed a significant increase in the motor skills compared with the control group. Moreover, the level of performance was significantly higher after 10 h/week compared to 4 h/week. These findings can be useful for standardizing PEPs in preschool settings so that they can be applied by teachers for planning effective programs for developing motor skills in early childhood.