The aim of the study was to identify the prevalence of newly diagnosed malignancies in patients with polymyalgia rheumatica (PMR) and giant cell arteritis (GCA), with the aid of 18F-FDG PET/CT scan compared to conventional imaging techniques: Chest X-ray (CXR) and abdominal ultrasound (US). Secondarily, to examine the relative diagnostic accuracy of these two imaging modalities for the detection of cancer. Eighty consecutive patients with newly diagnosed PMR, GCA, or concomitant PMR and GCA, were included and followed up for 40 weeks. All patients underwent an 18F-FDG PET/CT scan, CXR, and abdominal US at diagnosis. Imaging findings were dichotomously categorized into malignant or benign. Among 80 patients, three patients were diagnosed with seronegative rheumatoid arthritis and were excluded from the analysis. Of the remaining 77, 64 (83.1%) patients were diagnosed with pure PMR, 3 (3.9%) with pure GCA, and 10 (13.0%) with concomitant PMR and GCA. Five types of cancer that were more prevalent than the one-year prevalence of 1.2% among the background population were found in four (5.2%; 95%CI: 1.4–12.8%) patients. CXR/abdominal US could detect the solid cancer in one patient, whereas 18F-FDG PET/CT could identify all four solid cancers. Furthermore, four (5.2%; 95%CI: 1.4–12.8%) cases of monoclonal gammopathy of undetermined significance (MGUS) were found. An increase in C reactive protein (CRP) implicated an increased risk for cancer of 2.4% (OR: 1.024, 95%CI: 1.001–1.047; p = 0.041). 18F-FDG PET/CT can reveal occult cancers at an early stage with a high negative predictive value, and it is specifically beneficial in PMR/GCA patients with nonspecific symptoms.