This is a cross-sectional research focused on research evidences regarding the implementation of Physical Education (PE) programmes in Malaysian primary schools based on the perceptions of primary school PE teachers. The sample consisted of 1276 teachers from 248 randomly sampled primary schools in Peninsular Malaysia. The survey instrument collected demographic data and four implementation dimensions (Teaching Ability, Administration of PE Programme, PE Class Distribution & Non-human Factor). Questionnaires were mailed to schools identified using the Ministry of Education Malaysia’s master list and the response rate was 69%. The findings showed that there was a need to have specialist PE teachers as majority of the current teachers taught less than five PE periods per week and only 6.2% were PE majors. Independent sample t-tests conducted on teaching ability revealed that male teachers were more capable than female teachers in knowledge, managing and teaching sport and fitness activities and, detect and correct students’ errors. On administration of PE programme, male teachers agreed more than female teachers that administrators organized in-house training, discussed PE teaching assignment, discussed factors affecting PE teaching, and observed PE teaching. As regards to class distribution, male PE teachers agreed more than female teachers that administrators had discussion with them before PE teaching assignment and assignment was based on interest and qualification. T-test results also revealed that there were no differences on perception of non-human factor statements. It is recommended that further research on solving PE human resource problems be undertaken. Specifically, greater attention should be given to in-house training and monitoring of the implementation of PE programmes.