Obesity is associated with vitamin D (VD) deficiency and arterial stiffness. This randomized control trial assessed the effects of VD supplementation during a weight-loss program on carotid intima-media thickness (IMT) and carotid compliance in obese adolescents. Participants were randomly assigned to receive either a 12-week lifestyle program with VD supplementation (n = 13), a lifestyle program without VD supplementation (n = 13) or a control group composed of normal-weight adolescents (n = 18). Serum total and free 25-hydroxyvitamin D (25(OH)D), IMT and carotid compliance were measured before and after the trial. Insufficiency in 25(OH)D concentration was found in 73% of obese participants compared to 22% among controls. Obese adolescents had lower free 25(OH)D and displayed higher IMT but lower carotid compliance than controls. Free 25(OH)D and IMT were negatively correlated in adolescents displaying VD insufficiency at baseline. After three months, total and free 25(OH)D increased in both groups. The changes of IMT and carotid compliance were similar between groups. The changes in IMT were correlated with the changes in total 25(OH)D in obese adolescents with VD insufficiency at baseline (r = −0.59, p = 0.03). While the lifestyle program with VD supplementation did not affect carotid compliance, IMT reduction was improved in obese adolescents