Physical fitness is a powerful marker of health in youth. Studies in adolescents and adults suggest that higher fat mass is related to worse physical fitness. However, there is limited knowledge whether fat mass and fat-free mass are associated with physical fitness already in preschoolers. Baseline data from the MINISTOP (Mobile-based INtervention Intended to STop Obesity in Preschoolers) trial was utilized for this cross-sectional analysis. Body composition was assessed using air-displacement plethysmography. Fat mass index [fat mass (kg)/height² (m)] and fat-free mass index [fat-free mass (kg)/height² (m)] were used to provide height-adjusted measures of body composition. Physical fitness was measured using the PREFIT (FITness testing in PREschool children) battery, which assesses cardiorespiratory fitness, upper-body and lower-body muscular strength as well as motor fitness. In total, this study included 303 children (168 boys and 135 girls), who were on average 4.48 ± 0.15 years old. Higher fat mass index was associated with worse cardiorespiratory fitness (standardized ß = -0.17, p = 0.002), lower-body muscular strength (ß = -0.17, p = 0.003) and motor fitness (ß = -0.21, p