We investigated the role of Coefficient of Variation (CoV), a first-order texture parameter derived from 18F-FDG PET/CT, in the prognosis of Non-Small Cell Lung Cancer (NSCLC) patients. Eighty-four patients with advanced NSCLC who underwent 18F-FDG PET/CT before therapy were retrospectively studied. SUVmax, SUVmean, CoV, total Metabolic Tumor Volume (MTVTOT) and whole-body Total Lesion Glycolysis (TLGWB) were determined by an automated contouring program (SUV threshold at 2.5). We analyzed 194 lesions: primary tumors (n = 84), regional (n = 48) and non-regional (n = 17) lymph nodes and metastases in liver (n = 9), bone (n = 23) and other sites (n = 13); average CoVs were 0.36 ± 0.13, 0.36 ± 0.14, 0.42 ± 0.18, 0.30 ± 0.14, 0.37 ± 0.17, 0.34 ± 0.13, respectively. No significant differences were found between the CoV values among the different lesion categories. Survival analysis included age, gender, histology, stage, MTVTOT, TLGWB and imaging parameters derived from primary tumors. At univariate analysis, CoV (p = 0.0184), MTVTOT (p = 0.0050), TLGWB (p = 0.0108) and stage (p = 0.0041) predicted Overall Survival (OS). At multivariate analysis, age, CoV, MTVTOT and stage were retained in the model (p = 0.0001). Patients with CoV > 0.38 had significantly better OS than those with CoV ≤ 0.38 (p = 0.0143). Patients with MTVTOT ≤ 89.5 mL had higher OS than those with MTVTOT > 89.5 mL (p = 0.0063). Combining CoV and MTVTOT, patients with CoV ≤ 0.38 and MTVTOT > 89.5 mL had the worst prognosis. CoV, by reflecting the heterogeneity of glycolytic phenotype, can predict clinical outcomes in NSCLC patients.