Background: Exercise is currently seen as an effective treatment for major depressive disorder (MDD). However, existing studies have focused mainly on mild-to-moderate depression. The moderate positive effect of exercise found in meta-analyses concerning these studies differs, however, from the harsh daily clinical practice, when trying to implement exercise as an adjunctive treatment. We aimed to evaluate the feasibility of aerobic exercise in MDD and identify future problems for implementation. Methods: The EFFect Of Running Therapy on Depression (EFFORT-D) study was a randomized clinical trial examining the effectiveness of running therapy or Nordic walking in inpatients and outpatients with MDD. We conducted a process evaluation based on the method of Linnan and Steckler. Participant inclusion, dropout and no show were registered qualitatively and quantitatively. Results: The inclusion and delivered dose of the exercise interventions were limited (60 and 75%, respectively), leading to 80% less inclusion than foreseen. Motivational doubts were the main reason not to participate in the study. The unexpected high dropout rates (40% after 3 months and 80% after 12 months) were frequently related to lack of motivation due to disease characteristics and severity. The duration of the intervention, longer than 3 months was another underlying factor for poor adherence. Conclusions: Depression severity appeared to be the key factor determining dropout, followed by the duration of exercise intervention, expressed by a pre- and post-inclusion lack of motivation. Both running therapy and Nordic walking were apparently unsuitable for most patients with MDD in the current format. Emphasis on motivational issues is necessary from the early start of the intervention in these patients with MDD. Also a tailored and stepped-care approach is advised for future implementation.