Head and neck squamous cell carcinomas (HNSCC) can arise from the oral cavity, oropharynx, larynx or hypopharynx, and is the sixth leading cancer by incidence worldwide. The 5-year survival rate of HNSCC patients remains static at 40-60%. Hence, biomarkers which can improve detection of HNSCC or early recurrences should improve clinical outcome. Mass spectrometry-based proteomics methods have emerged as promising approaches for biomarker discovery. As one approach, mass-spectrometric identification of proteins shed or secreted from cancer cells can contribute to the identification of potential biomarkers for HNSCC and our understanding of tumor behavior. In the current study, mass spectrometry-based proteomic profiling was performed on the conditioned media (i.e. secretome) of head and neck cancer (HNC) cell lines (FaDu, UTSCC8 and UTSCC42a) in addition to gene expression microarrays to identify over-expressed transcripts in the HNSCC cells in comparison to a normal control cell line. This integrated data set was systematically mined using publicly available resources (Human Protein Atlas and published proteomic/transcriptomic data) to prioritize putative candidates for validation. Subsequently, quantitative real-time PCR (qRT-PCR), Western blotting, immunohistochemistry (IHC), and ELISAs were performed to verify selected markers. Our integrated analyses identified 90 putative protein biomarkers that were secreted or shed to the extracellular space and over-expressed in HNSCC cell lines, relative to controls. Subsequently, the over-expression of five markers was verified in vitro at the transcriptional and translational levels using qRT-PCR and Western blotting, respectively. IHC-based validation conducted in two independent cohorts comprising of 40 and 39 HNSCC biopsies revealed that high tumor expression of PLAU, IGFBP7, MMP14 and THBS1 were associated with inferior disease-free survival, and increased risk of disease progression or relapse. Furthermore, as demonstrated using ELISAs, circulating levels of PLAU and IGFBP7 were significantly higher in the plasma of HNSCC patients compared with healthy individuals.