Background: Individuals with anorexia nervosa (AN) tend to have rigid thoughts and behaviors regarding their body weight, body image, and eating habits. While a diagnosis of AN implies severe levels of impairment, AN traits can vary on a continuum within the population. However, little is known about how early markers of AN relate to rigid thought patterns and to what extent cognitive rigidity is already present in early childhood. We examined the association of set-shifting abilities as a measure of cognitive flexibility in preadolescents with AN-related features. Methods: Participants included 3,987 children participating in the Generation R Study, a Dutch population-based birth cohort. Set-shifting abilities (mother report) were assessed at 4 years of age, body mass index (BMI) was determined at 4 and 9 years and restrictive eating patterns (mother report) and body image (child report) were assessed at 9 years. Results: Lower set-shifting abilities at 4 years were associated with a lower BMI (β = −.44, p = 2.2 × 10−4) in girls, and more restrictive eating (β = 0.15, p = 2.7 × 10−6) in both boys and girls at 9 years of age. Moreover, set-shifting at age 4 was not associated with body image at age 9. Conclusion: These findings contribute to the idea that the association between set-shifting problems and AN-related features are present early in childhood, prior to the typical range of the onset of eating disorders (EDs). Longitudinal studies that capture the peak age for the development of EDs will be important to assess whether early cognitive inflexibility is an early marker of AN.