The purpose of this study was to determine the associations of device-based assessments of physical activity (PA) and health-related fitness (HRF) with gross motor skills (GMS) in preschool-aged children. Participants were 3- to 5-year-old children (N = 316; 49.6% female) who participated in the 2012 National Youth Fitness Survey. GMS was assessed using the gross motor quotient calculated from the Test for Gross Motor Development--Second Edition. PA was assessed using wrist-worn ActiGraph GT3X accelerometers with raw triaxial acceleration data summarized using monitor-independent movement summary units (MIMS). Analyzed metrics included average MIMS per day and peak 30-min MIMS. HRF assessment consisted of a plank score and a sum of skinfold assessment. Weighted hierarchical regressions tested the associations between PA, HRF, and GMS variables with a secondary weighted mediation analysis that examined whether HRF mediated the association between PA and GMS. Peak 30-min MIMS significantly correlated with GMS (b = 0.17, p = 0.005). Plank scores had the strongest correlation with GMS (b = 0.23, p = 0.004), and weighted mediation analyses revealed that plank scores partially mediated the association between peak 30-min MIMS and GMS (indirect effect = 0.03, p = 0.01, 23.1% mediation). Peak 30-min MIMS significantly associated with GMS in preschool children, an association partially mediated by core muscular endurance.