Physical activity (PA) and body mass index (BMI) are consistently associated with motor coordination (MC) in children. However, we know very little how BMI in early childhood associates with MC later in childhood. This study investigated associations between BMI in early childhood and BMI, PA, and MC in middle childhood. Children aged 5 to 7 years (n = 64, 32 girls) were measured for MC using Körperkoordinationstest für Kinder (KTK) and for moderate-to-vigorous PA (MVPA) using triaxial accelerometers. Prevailing body weight and height were measured, and information on weight and height in early years was based on parental report of child health care report cards. Age-adjusted BMIz scores were calculated on the basis of international growth curve references. Associations and the explained variability of MC were investigated by Pearson correlations and a hierarchical multiple regression analysis. Age and MVPA were found to be significantly associated with MC at middle childhood, in general. BMIz at middle childhood and at ages 4 and 5 years inversely explained 12% (p < 0.05), 6% (p > 0.05), and 7% (p > 0.05) of the variation in MC in girls after adjusting for covariates, respectively. In boys, BMIz scores did not show any trend of association with MC. This study suggests sex-specific mechanisms in the interplay between BMI and motor development in childhood.