Cancer stem cell-related (CSC) markers have been suggested to have promising potentials as novel types of prognostic and predictive markers in gliomas. However no single CSC-related marker is currently used in clinical decisions. The aim of this study was to investigate the prognostic value of CD133 and nestin separately and in combination using a novel quantitative approach in a well-characterized population-based cohort of glioma patients. The expression of CD133 and nestin was measured by systematic random sampling in stained paraffin sections from 239 glioma patients diagnosed between 2005 and 2009. We found that the expression of CD133 did not correlate with WHO grade, and there was no association with overall survival (OS). The level of nestin correlated positively with WHO grade. In patients with WHO grade II tumors, a high level of nestin was associated with short progression-free survival (PFS) in multivariate analysis. High levels of co-localization were associated with poor PFS in patients with WHO grade II tumors, but not with OS. We conclude that CD133 was not an independent prognostic factor, but a high level of nestin was associated with poor PFS in patients with WHO grade II tumors. The combination of double-immunofluorescence and automated analysis seems to be a feasible and reproducible approach for investigation of the prognostic potential of biomarkers.