Subclinical cardiovascular disease (CVD) may be associated with both adipose and skeletal muscle tissues in the abdomen. Accordingly, we examined whether subcutaneous, intermuscular, and visceral adipose tissue, as well as abdominal lean muscle, were associated with the presence and extent of vascular calcification in multiple vascular beds. Three hundred and ninety four patients (58.1% men) underwent electron beam computed tomography (EBCT) scans as part of routine health maintenance screening. The coronary and carotid calcium scores were analyzed at the time of the scan, whereas the other calcium scores, as well as the body composition analyses, were analyzed retrospectively. Mean age was 55.2 ± 11.1 years and BMI was 26.9 ± 4.2. The prevalence of any calcification in the carotids, coronaries, thoracic aorta, abdominal aorta, and iliacs was 30.1, 60.1, 39.8, 55.7, and 56.8%, respectively. Compared to those with calcification in different vascular beds, those without vascular calcification generally had significantly more lean muscle and less adipose tissue. In separate multivariable logistic models, a 1 s.d. increment in the ratio of abdominal and visceral fat to total area of each corresponding compartments was significantly associated with an increased odds for the presence of thoracic aortic calcium (odds ratio (OR) = 1.6, 1.5, respectively; P = 0.01 for both). Conversely, increases in abdominal lean muscle were associated with significantly decreased odds of thoracic aortic calcification (OR = 0.34; P ≤ 0.01). A similar pattern of associations existed among the other vascular beds. Also, the association between lean muscle and vascular calcification was independent of visceral adipose tissue. In conclusion, adipose tissue was positively and lean body mass inversely associated with prevalent aortic calcification.