Background: Motor skill (MS) competence is an important contributing factor for healthy development. Purpose: The goal was to test the effectiveness of primary school physical education (PE) on MS and physical fitness (PF) development. Methods: Three classes (n = 60, aged 9.0 ± 0.9) were randomly assigned to three diverse conditions during a school year: two PE lessons/week (PE-2), three PE lessons/week (PE-3), and no PE lessons control group (CG). BMI, skinfolds, PF (9-min run/walk, sit-up, modified pull-ups), gymnastics, soccer, handball, basketball and track-and-field skills were evaluated. Effect sizes (d) were reported as magnitude of change. Results: Skinfolds significantly increased only in CG (d = 1.21). PF composite z-scores improved in PE-3 (d = 0.61), but decreased in PE-2 (d = 0.57), and had no changes in CG. Statistically significant improvement was verified in gymnastics and handball skills in both experimental groups (gymnastic: d = 2.95 and d = 2.61 for PE-3 and PE-2, respectively; handball: d = 1.87 and d = 0.57 for PE-3 and PE-2, respectively), and no changes were seen in CG. In soccer, there were improvements only in the PE-3 (d = 0.55), and in basketball only in PE-2 (d = 0.46). There were no changes in any group for track-and-field skills. Conclusions: PE programs can effectively promote PF and MS development.