The goals of this study were to determine the feasibility of engaging youth with major depressive disorder (MDD) in a multimodal exercise intervention (Healthy Body Healthy Mind) plus usual care and to evaluate the magnitude of its effects on psychological, physical fitness, and biomarker outcomes to inform a future randomized controlled trial. Youth (15 to 25 y of age) with MDD diagnosed using the Structured Clinical Interview for DSM-IV Axis I Disorders (SCID-I) were eligible to participate. Feasibility measures included recruitment, retention, and program adherence rates. The exercise program consisted of a single session of motivational interviewing to enhance exercise adherence, then 1-hour, small-group supervised exercise sessions 3 times per week for 12 weeks. Assessments were administered at baseline and at 12 weeks. Depression symptoms were assessed using the Beck Depression Inventory (BDI-II). Physical fitness and blood biomarkers were also measured. Three males and 10 females with MDD, who were 18 to 24 years of age, participated. Retention at 12 weeks was 86%, and attendance at exercise sessions averaged 62%±28%. After 12 weeks, 69% of participants experienced a remission of MDD based on the SCID. Mean BDI-II scores decreased from 31.9±9.1 to 13.1±10.1 [Cohen d effect size (ES)=1.96]. Improvements were observed in upper (ES=0.64) and lower (ES=0.32) body muscular endurance. Exercise session attendance was moderately correlated with changes in BDI-II scores (Pearson r=0.49). It appears feasible to attract and engage some youth with MDD in an exercise intervention. The positive impact on depression symptoms justifies further studies employing exercise interventions as an adjunct to routine care for young people with MDD.