Abstract Background Children’s fussy eating behavior has been related to both underweight and overweight in cross-sectional studies, but the direction of these associations and the relation with more detailed measures of body composition remains unclear. We aimed to examine whether fussy eating at age 4 years is longitudinally related to body mass index (BMI), fat mass index (FMI) and fat-free mass index (FFMI) at 6 years of age. Methods This study was embedded in Generation R, a population-based, prospective cohort. Data were available for 4191 children. The Children’s Eating Behaviour Questionnaire (CEBQ), administered at age 4 years, was used to derive a fussy eating profile. This profile is characterized by high scores on food avoidant scales and low scores on food approach scales. At age 6 years, height and weight were measured at our research center. Body fat and fat-free mass were measured using Dual-energy-X-ray absorptiometry. We used age- and sex-specific standard deviation scores (SDS) for all outcomes. Results After adjustment for confounders, the fussy eating profile was related to lower BMI-SDS (B = −0.37, 95 % CI: −0.47;−0.26), lower FMI-SDS (B = −0.22, 95 % CI: −0.33;−0.12) and lower FFMI-SDS (B = −0.41, 95 % CI: −0.54;−0.29). When adjusting for baseline BMI at 4 years, the fussy eating profile predicted a 0.11 lower BMI-SDS at age 6 (95 % CI: −0.19;−0.04). This change in BMI was mainly due to a decrease in FFMI (B = −0.19, 95 % CI: −0.29;−0.09). Fussy eaters also had a higher risk of becoming underweight than non-fussy eaters (OR = 2.28, 95 % CI: 1.34;3.87). Conclusions Our findings suggest that young fussy eaters are at risk of having a lower fat free mass and of becoming underweight over a 2-year period. This implies that fussy eaters may benefit from careful monitoring to prevent an adverse growth development.