Behavioral, biological, and social correlates may be related to the association between executive function (EF) and physical activity (PA), when considering such variables as an integrated and non-linear system. Thus, the aim of the present study was to investigate the relationships between EF, PA and associated correlates in low-income preschoolers according to a network perspective. Thus, 142 preschoolers of both sexes, age 3-to-5-years-old (51% girls) were analyzed. Light, moderate and vigorous PA, cardiorespiratory fitness (CRF), body mass index, family income, preterm birth, presence of siblings, presence of other children at home and the child’s primary caregiver were assessed. Our results showed that EF was positively associated with age (b = 0.47), child’s primary caregivers (b = 0.37), moderate PA (b = 0.30) and CRF (b = 0.25). Negative associations were seen with preterm birth (b = −0.50), vigorous PA (b = −0.34), presence of other children at home (b = −0.25), and sex (b = −0.33). The network’s centrality indicators highlighted preterm birth and moderate PA as the most important variables in the network. Future interventions aiming to increase low-income preschoolers’ EF should focus on increasing moderate PA, with special attention to preterm children.