To identify molecular signatures and establish a new diagnostic model for progressive oral squamous cell carcinoma (OSCC). Total RNAs were isolated from primary OSCCs from both node-positive and -negative patients and used in cDNA microarray analysis. To identify marker genes representing a malignant phenotype, their expression was further examined by quantitative reverse transcription-PCR (QRT-PCR) in 64 OSCC tissues. Using Fisher's linear discriminant analysis (LDA) fitted with a stepwise increment method, we created discriminatory predictor models. The stability of these models was examined using leave-one-out cross validation. Immunohistochemical analysis was performed. Among the 16,600 possible target cDNAs in the array analysis, 83 genes demonstrated significantly differential signals (>2-fold). We further identified 53 marker genes that can be implicated in the Yamamoto-Kohama's (YKs) mode of invasion for OSCCs (P < 0.06). Using LDA fitted with a stepwise increment method, we created four discriminatory predictor models based on 16- to 25-gene signatures which could best distinguish the five established grades of YKs mode of invasion. Leave-one out validation demonstrated that the stability of these models was 92-95%. For validation, we also examined an independent set of 13 primary OSCCs; the predictor models determined the invasion status from 77% to 100% (on average, 85%) fidelity with the pathological observations. TGM3 protein expression was markedly suppressed in highly invasive OSCCs. We reveal novel gene expression alterations during the progression of OSCC, and have constructed prediction models for the evaluation of the invasion status of these cancers.