Prolonged fasting may benefit metabolic health, but data in healthy individuals remain limited. We performed a randomized, waitlist-controlled study (LEANER study), with 38 healthy participants completing a 5-day-fasting intervention with 12-week follow-up. Fasting acutely lowered body mass index (BMI), via fat mass loss. These changes partially persisted at follow-up. Fasting altered the gut microbiome composition and induced metabolite shifts in plasma and feces. Changes to gut microbiome alpha diversity after fasting correlated with baseline microbiome diversity. Long-term BMI response at follow-up could be predicted through machine learning (ML) using baseline microbiome and clinical data, highlighting an unknown Faecalibacterium sp., Oscillibacter sp. 50_27, LDL cholesterol, and systolic blood pressure as key predictors. This ML model was validated in independent patient cohorts with metabolic syndrome and multiple sclerosis. These findings support prolonged fasting as an effective metabolic intervention and demonstrate that individual responses to fasting interventions can be predicted using pre-intervention features.