Myeloid-derived suppressor cells (MDSCs) represent a heterogeneous population of cells with immunosuppressive properties and might confer to worse prognosis in cancer patients. The presence of phenotypically newly described subpopulations of MDSCs and their association with the clinical outcome were investigated in non-small cell lung cancer (NSCLC) patients. The percentages and correlation between MDSCs and distinct immune cells in the peripheral blood of 110 chemotherapy-naive patients before treatment and healthy controls were investigated using flow cytometry. Two monocytic [CD14(+)CD15(-)CD11b(+)CD33(+)HLA-DR(-)Lin(-) and CD14(+)CD15(+)CD11b(+)CD33(+)HLA-DR(-)Lin(-)] and a granulocytic [CD14(-)CD15(+)CD11b(+)CD33(+)HLA-DR(-)Lin(-)] subpopulations of MDSCs were identified, expressing inducible nitric oxide synthase, and reactive oxygen species, respectively. Increased percentages of both monocytic-MDSCs' subpopulations were inversely correlated to dendritic/monocyte levels (P ≤ 0.04), while granulocytic-MDSCs were inversely correlated to CD4(+) T cells (P = 0.006). Increased percentages of monocytic-MDSCs were associated with worse response to treatment (P = 0.02) and patients with normal levels of CD14(+)CD15(+)CD11b(+)CD33(+)HLA-DR(-)Lin(-) had longer overall survival and progression free-survival compared to those with high levels (P = 0.008 and P = 0.005, resp.). Multivariate analysis revealed that the increased percentages of CD14(+)CD15(+)CD11b(+)CD33(+)HLA-DR(-)Lin(-) MDSCs were independently associated with decreased progression free-survival and overall survival. The data provide evidence that increased percentages of new monocytic-MDSCs' subpopulations in advanced NSCLC patients are associated with an unfavourable clinical outcome.