We recently showed that upregulation of a key oncogene FOXM1 precedes head and neck squamous cell carcinoma (HNSCC) malignancy. Furthermore, we also identified a centrosomal protein CEP55 and a DNA helicase/putative stem cell marker HELLS, which are both downstream targets of FOXM1. In this study, we have investigated the expression profiles of CEP55 and HELLS using immunohistochemistry and quantified by digital densitometry in a tissue panel (20 samples) consisting of normal oral mucosa, dysplasias, HNSCC and lymph node metastasis (LnMet) samples. Furthermore, we corroborated our findings using absolute real-time PCR (qPCR) on a panel of 12 primary normal human oral keratinocytes, five dysplasia and 10 HNSCC cell lines. Finally, we validated our study using bioinformatics microarray analysis on an independent HNSCC patient cohort (four normal and 16 tumours). In normal oral mucosa, CEP55 protein was detected at very low level within the upper differentiated layers. In contrast, CEP55 was highly expressed in oral dysplasia whereas only moderate expression was detected in HNSCC and LnMet. Low level of HELLS expression was detected in the basal cell layer of the normal oral mucosa, moderate level was seen in dysplasia and high levels in both HNSCC and LnMet. These expression patterns were consistent with both qPCR data from the cell line panel and microarray data analysis of TNM-stage defined HNSCC samples confirming the progressive expression pattern of CEP55 and HELLS. To our knowledge, this is the first pilot study demonstrating that both CEP55 and HELLS mRNA and protein expression positively correlate with pre-malignancy and HNSCC progression. This study provides strong evidence that CEP55 and HELLS may be used in conjunction with FOXM1 as a biomarker set for early cancer detection and indicators of malignant conversion and progression.