Background: Despite extensive research on body weight and cardiovascular risk, the mechanistic relationship between weight loss and coronary plaque modification has not been adequately addressed. This study aimed to determine the association between body composition dynamics and low-attenuation coronary plaque (LAP) burden. Methods: Eighty-nine participants (40% women, 60 ± 7.7 years) of the Dietary Intervention to Stop Coronary Atherosclerosis in Computed Tomography (DISCO-CT) study with non-obstructive atherosclerosis with nonobstructive atherosclerosis confirmed in computed tomography angiography (CCTA), a randomized (1:1), prospective, single-center study were included into the analysis. Patients were randomly assigned to either experimental arm (intensive diet and lifestyle intervention atop optimal medical therapy, n = 45) or control arm (optimal medical therapy alone, n = 44) over 66.8 ± 13.7 weeks. Changes (∆) in body mass (BM) and body composition parameters, including total body fat (TBF), skeletal muscle mass (SMM), and fat-to-muscle ratio (FMR), measured with bioimpedance analyzer were compared with CCTA-measured ∆LAP. Coronary plaque analysis was performed using the 2 × 192 dual-energy scanner (Somatom Force, Siemens, Germany), while quantitative coronary plaque measurements were performed using a semi-automated plaque analysis software system (QAngioCT v3.1.3.13, Medis Medical Imaging Systems, Leiden, The Netherlands). Results: Significant intergroup differences were found for ∆BM (−3.6 ± 4.9 kg in the experimental vs. −1.4 ± 2.9 kg in the control group, p = 0.015), ∆TBF (−3.4 ± 4.8% in the experimental vs. 1.1 ± 5.5% in the control arm, p < 0.001), ∆SMM (1.9 ± 2.8% in the experimental vs. −0.7 ± 3.2% in the control arm, p < 0.001), and FMR [−12.9 (−21.2; −4.3)% in the experimental vs. 3.1 (−5.3; 10.7)% in the control arm, p < 0.001]. ∆LAP did not differ significantly between the study arms; however, in the whole study population, ∆LAP was positively correlated with ∆BM, ∆TBF, and ∆FMR (r = 0.45, p < 0.001; r = 0.300, p = 0.004; r = 0.233, p = 0.028, respectively), and negatively with ∆SMM (r = −0.285, p = 0.007). Multivariate linear regression analysis revealed the association of ∆LAP with ∆BM, ∆TBF, and ∆FMR. Conclusions: The study intervention resulted in BM reduction characterized by fat loss, skeletal muscle gain, and increased FMR. This weight loss pattern may lead to a reduction in high-risk coronary plaque. Compared to a simple weight control, tracking body composition changes over time can provide valuable information on adverse coronary plaque modification.