Head and neck cancer (HNSCC) is one of the most distressing human cancers, causing pain and affecting the basic survival functions of breathing and swallowing. Mortality rates have not changed despite recent advances in radiotherapy and surgical treatment. We have compared the expression of over 13,000 unique genes in 7 cases of matched HNSCC and normal oral mucosa. Of the 1,260 genes that showed statistically significant differences in expression between normal and tumor tissue at the mRNA level, the three top ranking of the top 5% were selected for further analysis by immunohistochemistry on paraffin sections, along with the tumor suppressor genes p16 and p53, in a total of 62 patients including 55 for whom >4-year clinical data was available. Using univariate and multivariate survival analysis, we identified SPARC/osteonectin as a powerful independent prognostic marker for short disease-free interval (DFI) (p < 0.002) and poor overall survival (OS) (p = 0.018) of HNSCC patients. In combination with other ECM proteins found in our analysis, PAI-1 and uPA, the association with DFI and OS became even more significant (p < 0.001). Our study represents the first instance of SPARC as an independent prognostic marker in HNSCC.