The aim of the present study was to investigate effects of aerobic interval training (AIT) versus moderate continuous training (MCT) on coronary atherosclerosis in patients with significant coronary artery disease on optimal medical treatment. Thirty-six patients were randomized to AIT (intervals at ≈ 90% of peak heart rate) or MCT (continuous exercise at ≈ 70% of peak heart rate) 3 times a week for 12 weeks after intracoronary stent implantation. Grayscale and radiofrequency intravascular ultrasounds (IVUS) were performed at baseline and follow-up. The primary end point was the change in plaque burden, and the secondary end points were change in necrotic core and plaque vulnerability. Separate lesions were classified using radiofrequency IVUS criteria. We demonstrated that necrotic core was reduced in both groups in defined coronary segments (AIT −3.2%, MCT −2.7%, p <0.05) and in separate lesions (median change −2.3% and −0.15 mm³, p <0.05). Plaque burden was reduced by 10.7% in separate lesions independent of intervention group (p = 0.06). No significant differences in IVUS parameters were found between exercise groups. A minority of separate lesions were transformed in terms of plaque vulnerability during follow-up with large individual differences between and within patients. In conclusion, changes in coronary artery plaque structure or morphology did not differ between patients who underwent AIT or MCT. The combination of regular aerobic exercise and optimal medical treatment for 12 weeks induced a moderate regression of necrotic core and plaque burden in IVUS-defined coronary lesions.