Major depressive disorder (MDD) is the most common mental disorder and deficits in neuroplasticity are discussed as one pathophysiological mechanism. Physical activity (PA) enhances neuroplasticity in healthy subjects and improves clinical symptoms of MDD. However, it is unclear whether this clinical effect of PA is due to restoring deficient neuroplasticity in MDD. We investigated the effect of a 3-week PA program applied on clinical symptoms, motor excitability and plasticity, and on cognition in patients with MDD (N = 23), in comparison to a control intervention (CI; N = 18). Before and after the interventions, the clinical symptom severity was tested using self- (BDI-II) and investigator- (HAMD-17) rated scales, transcranial magnetic stimulation (TMS) protocols were used to test motor excitability and paired-associative stimulation (PAS) to test long-term-potentiation (LTP)-like plasticity. Additionally, cognitive functions such as attention, working memory and executive functions were tested. After the interventions, the BDI-II and HAMD-17 decreased significantly in both groups, but the decrease in HAMD-17 was significantly stronger in the PA group. Cognition did not change notably in either group. Motor excitability did not differ between the groups and remained unchanged by either intervention. Baseline levels of LTP-like plasticity in the motor cortex were low in both groups (PA: 113.40 +/- 2.55%; CI: 116.83 +/- 3.70%) and increased significantly after PA (155.06 +/- 10.48%) but not after CI (122.01 +/- 4.1%). Higher baseline BDI-II scores were correlated with lower levels of neuroplasticity. Importantly, the more the BDI-II score decreased during the interventions, the stronger did neuroplasticity increase. The latter effect was particularly strong after PA (r = -0.835; p < 0.001). The level of neuroplasticity related specifically to the psychological/affective items, which are tested predominantly in the BDI-II. However, the significant clinical difference in the intervention effects was shown in the HAMD-17 which focuses more on somatic/neurovegetative items known to improve earlier in the course of MDD. In summary, PA improved symptoms of MDD and restored the deficient neuroplasticity. Importantly, both changes were strongly related on the individual patients' level, highlighting the key role of neuroplasticity in the pathophysiology and the clinical relevance of neuroplasticity-enhancing interventions for the treatment of MDD.