Background: To examine the longitudinal association between frailty criteria and depression (DEP) in a large sample of older Europeans using decision tree models, and to examine complex relationships between frailty criteria and DEP symptomatology. Methods: Data come from waves six and eight of the Population Survey of Health, Ageing and Retirement in Europe. DEP was assessed using the EURO-D scale (wave 8) and frailty (wave 6). We included 27,122 people (56.9% women), aged 50 or over. Results: Women indicated a higher rate of DEP (29.0%), as well as a higher prevalence of pre-frailty (21.6%) and frailty (10.8%) than men. For both sexes, fatigue, weight loss, and slowness indicated an increased chance of DEP 5 years later. MPA (moderate physical activity) and grip strength were considered longitudinally protective factors for DEP. The highest prevalence of DEP symptomatology 5 years later was 50.3%, pointing to those with fatigue and slowness. Among women, the highest incidence of DEP was 66.8%, identified through fatigue, slowness, and low MPA. Conclusions: Strategies to reduce frailty and DEP in older European adults may include the creation of policies that encourage the promotion of physical capacity to reach MPA levels, as well as an improvement in muscular strength.