High competence in fundamental motor skills (FMS) and adequate physical fitness (PF) levels allow for a solid foundation for acquiring an active and healthy lifestyle during childhood and adolescence. This study aimed to compare gender and age groups and identify the correlations between FMS and PF in students in the early elementary school years using a cross-sectional design, descriptive, and correlational approach. We used a structured questionnaire to gather information about the sample’s sociodemographic characteristics. The economic profile was categorized using the Brazil Social Economic Status Criterion. We collected FMS data using the Furtado-Gallagher Children Observational Movement Pattern Assessment System (FG-COMPASS) and used the Brazil Sports Project Battery Test to measure PF levels. Statistical analyses used descriptive and inferential measures to determine the differences between groups in FMS and PF levels. In addition, hierarchical regression methods were used to identify the association between FMS and PF, controlled by sociodemographic factors. The study involved 720 students of both genders from grades 1 to 5 in an elementary school in a municipality in the western region of the Paraná state in Brazil. The results showed significant differences in motor skills and physical fitness based on gender and age. The hierarchical regression model showed different combinations of flexibility, abdominal resistance, upper limb strength, agility, speed, and lower limb strength, which explained 33.7% of the variability in the global FMS index, 41% of the variability in manipulative skills, and 12.7% of the variability in locomotor skills. In addition, there was a positive association between FMS and PF related to neuromuscular development for both sexes, regardless of age.