Background: Health organisations such as the United Nations continue to place an expectation on school physical education (PE) programmes and wider school strategies to ensure students develop physical literacy and receive the well-established benefits of meeting physical activity guidelines. Barriers to meet this expectation such as lack of trained PE teachers, lack of time and greater emphasis on academic achievement are ongoing challenges to schools. The purpose of this study was to evaluate the impact of the multi-component Physical Education Physical Literacy (PEPL) intervention, designed to improve students’ fundamental movement skill, perceived physical abilities and level of physical activity. Method: A qualified PE teacher implemented the PEPL intervention across seven schools, and another seven schools formed a control group as part of a randomised cluster-based trial. Grade 5 students (N = 318, age 10.4 years ± SD 0.4) completed assessments of physical activity, fundamental movement skill, attitudes towards PE, and self-perceptions of physical abilities before and after a 33-week intervention. Intervention effects were examined using general linear mixed models. Post-intervention focus groups with students were used to develop insights into experiences and outcomes. Results: With no significant gender interactions, the PEPL approach led to enhanced object control skills (β = 1.62; SE = 0.61; p = 0.008), with little evidence of any other fundamental movement skill improvements in excess of those in the control group. There was also modest evidence for an effect on accelerometer measured moderate-to-vigorous physical activity (MVPA) during school time (β = 4.50; SE = 2.39; p = 0.058), but this was not accompanied by any significant intervention effect over the entire week. Questionnaires indicated students in the PEPL programme became less satisfied with their own sporting ability (β = −0.20; SE = 0.08; p = 0.013) but qualitative data analyses suggested that they enjoyed the PEPL approach experience, becoming more motivated and confident in their physical abilities. Conclusions: Evidence of enhanced object control skill, increased confidence and motivation to be physically active, and moderate evidence of more MVPA during school time, indicate that the introduction of the PEPL approach contributed to the development of student physical literacy. A decrease in perceived sporting competence warrants greater attention on student’s self-perceptions in future iterations of the intervention. Trial registration: Australian New Zealand Clinical Trials Registry identifier: ACTRN12615000066583.