Exercise intervention studies in mild cognitive impairment (MCI), a prodromal stage of Alzheimer's disease (AD), have demonstrated inconsistent yet promising results. Addressing the limitations of previous studies, this trial investigated the effects of a 12-month structured exercise program on the progression of MCI. The NeuroExercise study is a multicenter randomized controlled trial across three European countries (Ireland, Netherlands, Germany). Hundred and eighty-three individuals with amnestic MCI were included and were randomized to a 12-month exercise intervention (3 units of 45 min) of either aerobic exercise (AE; n = 60), stretching and toning exercise (ST; n = 65) or to a non-exercise control group (CG; n = 58). The primary outcome, cognitive performance, was determined by an extensive neuropsychological test battery. For the primary complete case (CC) analyses, between-group differences were analyzed with analysis of covariance under two conditions: (1) the exercise group (EG = combined AE and ST groups) compared to the CG and (2) AE compared to ST. Primary analysis of the full cohort (n = 166, 71.5 years; 51.8% females) revealed no between-group differences in composite cognitive score [mean difference (95% CI)], 0.12 [(-0.03, 0.27), p = 0.13] or in any cognitive domain or quality of life. VO2 peak was significantly higher in the EG compared to the CG after 12 months [-1.76 (-3.39, -0.10), p = 0.04]. Comparing the two intervention groups revealed a higher VO2peak level in the aerobic exercise compared to the stretching and toning group, but no differences for the other outcomes. A 12-month exercise intervention did not change cognitive performance in individuals with amnestic MCI in comparison to a non-exercise CG. An intervention effect on physical fitness was found, which may be an important moderator for long term disease progression and warrants long-term follow-up investigations. Clinical Trial Registration: https://clinicaltrials.gov/ct2/show/NCT02913053, identifier: NCT02913053.