Lifestyle behavioral habits such as excess screen time (ST), a lack of physical activity (PA), and high energy-dense food consumption are associated with an increased risk of children being overweight or obese. This study aimed to (1) track longitudinal adherence to PA and ST recommendations at baseline (T0) and follow-up (T1) and (2) assess the association between changes in adherence to PA and ST recommendations and food and beverage consumption at follow-up. The present study included 2321 preschool children (3.5 to 6) participating in the multicenter ToyBox-study. A lineal mixed effects model was used to examine the association between different types of food and beverages and their relationship with changes in adherence to PA and ST recommendations. Approximately half of the children (50.4%) did not meet the PA and ST recommendations at both baseline and follow-up. However, only 0.6% of the sample met both PA and ST recommendations. Preschool children who met both recommendations consumed fewer fizzy drinks, juices, sweets, desserts, and salty snacks and consumed more water, fruits and vegetables, and dairy products than did those not meeting both recommendations. In conclusion, the proportion of European preschool children adhering to both PA and ST recommendations was very low and was associated with a low consumption of energy-dense foods.