The aims of this study were to determine proficiency levels of fundamental movement skills using cluster analysis in a cohort of U.K. primary school children; and to further examine the relationships between fundamental movement skills proficiency and other key aspects of health-related physical activity behavior. Participants were 553 primary children between 9- and 12-years old, 294 boys and 259 girls, who were assessed across eight different fundamental movement skills. Physical activity behaviors included markers of physical fitness, recall of physical activity behavior, and physical self-concept. Hierarchical cluster analysis was used to classify groups based on fundamental movement skills proficiencies and discriminant analysis to predict fundamental movement skills proficiency based upon the physical activity variables. This interpretation of fundamental movement skills performance revealed distinct groups of fundamental movement skills proficiency in both genders with several gender-specific components of physical activity shown to discriminate children with differing levels of fundamental movement skills proficiency (p < 0.05, r > 0.40).