This study aimed to examine associations between gross motor skills and executive functions (EF) in a large sample of Australian preschool-aged children. Of 566 children (mean age = 3.2 ± 0.4 years, 51.2% girls), locomotor, object control, and total skill competence were significantly associated with visual spatial working memory and inhibition (p < 0.05). Total skill competence was associated with shifting and locomotor skills were significantly associated with self-regulation (p < 0.05). Static balance was significantly associated with inhibition and shifting (p < 0.05). In boys, an association between object control skills and visual spatial working memory was observed. In girls, an association between static balance and visual spatial working memory, phonological working memory, and shifting was observed. The identification of significant associations between gross motor skills and different EFs is an important contribution to the growing evidence on the relationship between motor skills and EFs in early childhood.