(1) The current literature contains several studies investigating the correlation between dual-energy-derived iodine concentration (IC) and positron emission tomography (PET)-derived Flourodeoxyglucose (¹⁸F-FDG) uptake in patients with non-small-cell lung cancer (NSCLC). In previously published studies, either the entire tumor volume or a region of interest containing the maximum IC or ¹⁸F-FDG was assessed. However, the results have been inconsistent. The objective of this study was to correlate IC with FDG both within the entire volume and regional sub-volumes of primary tumors in patients with NSCLC. (2) In this retrospective study, a total of 22 patients with NSCLC who underwent both dual-energy CT (DE-CT) and ¹⁸F-FDG PET/CT were included. A region of interest (ROI) encircling the entire primary tumor was delineated, and a rigid registration of the DE-CT, iodine maps and FDG images was performed for the ROI. The correlation between tumor measurements and area-specific measurements of IC_peak and the peak standardized uptake value (SUV_peak) was found. Finally, a correlation between tumor volume and the distance between SUV_peak and IC_peak centroids was found. (3) For the entire tumor, moderate-to-strong correlations were found between SUV_max and IC_max (R = 0.62, p = 0.002), and metabolic tumor volume vs. total iodine content (R = 0.91, p < 0.001), respectively. For local tumor sub-volumes, a negative correlation was found between IC_peak and SUV_peak (R = −0.58, p = 0.0046). Furthermore, a strong correlation was found between the tumor volume and the distance in millimeters between SUV_peak and IC_peak centroids (R = 0.81, p < 0.0001). (4) In patients with NSCLC, high FDG uptakes and high DE-CT-derived iodine concentrations correlated on a whole-tumor level, but the peak areas were positioned at different locations within the tumor. ¹⁸F-FDG PET/CT and DE-CT provide complementary information and might represent different underlying patho-physiologies.