Understanding how changes in nutritional status influence musculoskeletal recovery after falling remains unclear. We explored associations between changes in nutritional status and musculoskeletal health in 106 community-dwelling older adults aged ≥65 years, who attended the Falls and Fractures Clinic at Sunshine Hospital in St Albans, Australia after falling. At baseline and after 6 months, individuals were assessed for Mini Nutritional Assessment (MNA®), grip strength, gait speed, Timed Up and Go (TUG) test, Short Physical Performance Battery (SPPB), and bone turnover marker levels. Associations were examined using multiple linear regression, adjusted for baseline covariates and post-fall care plans. Over 6 months, the prevalence of malnutrition or risk thereof decreased from 29% to 15% using MNA <24/30. Specifically, 20 individuals (19%) improved, 7 (7%) deteriorated, and 73 (69%) maintained nutritional status, including 65 (61%) who remained well-nourished and 8 (8%) who remained malnourished/at risk. A 1-point increase in MNA score over 6 months was associated with an increase of 0.20 points (95% confidence interval 0.10, 0.31, p < 0.001) in SPPB score. Improvement in nutritional status was associated with improvement in physical performance, providing a basis for interventional studies to ascertain causality and evaluate nutritional models of care for post-fall functional recovery in older adults.