Executive function is foundational for cognitive development. Previous research has shown both gross motor skills and physical activity to be related to executive function. However, evidence for these relationships in the preschool years, as well as in low- and middle-income countries is lacking. Therefore, this study aimed to investigate the relationships between components of executive function (inhibition, shifting and working memory) and gross motor skills (locomotor skills and object control skills) in a sample of preschool children from urban and rural low-income settings in South Africa. Results revealed that inhibition and working memory, but not shifting, were associated with gross motor skills. More specifically: inhibition was associated with both locomotor [beta = 0.20, p = 0.047] and object control skills [beta = 0.24, p = 0.024], whereas working memory was only associated with locomotor skills [beta = 0.21, p = 0.039]. Physical activity was not associated with inhibition and shifting but was negatively associated with working memory. These results elaborate a growing evidence base linking executive function and gross motor skills in the early years, and it is the first to look at specific associations of locomotor and object control skills with executive function in the South African context (a low- and middle-income country).