Pseudoxanthoma elasticum (PXE) is a genetic disease characterized by the calcification of elastin fibers. Our aim was to quantify vascular calcification in the arteries and the deposition of 18F-sodium-fluoride (18F-NaF) in the skin and vessel walls with positron emission tomography/computed tomography. This was an observational study including 18 patients with PXE. Vascular calcification was measured in Agatston units, and deposition in the skin and vessel walls was shown using target-to-background ratio (TBR). Severity of the disease was scored by Phenodex. We found higher vascular calcification in the popliteal, femoral, and aortic arch vessels compared to other vascular regions; however, the uptake of radiotracer was the highest in the aorta and femoral arteries. In the skin, the highest uptake was observed in the neck and the axillae. There was no significant association between 18F-NaF deposition in the arteries or skin and the global Phenodex score. In contrast, the Phenodex score was significantly associated in univariate analyses with the averaged vascular calcium score (p < 0.01). In the neck, patients with higher skin Phenodex scores exhibited higher radiotracer uptake. As a conclusion, because vascular calcification is physiological, our data suggested that the detection of cutaneous (neck) 18F-NaF deposits might serve to monitor the calcification process in the short-term for patients with PXE.