Background: Current histopathological classification and TNM staging have limited accuracy in predicting survival and stratifying patients for appropriate treatment. The goal of the study is to determine whether the expression pattern of functionally important regulatory proteins can add additional values for more accurate classification and prognostication of non-small lung cancer (NSCLC). Methods: The expression of 108 proteins and phosphoproteins in 30 paired NSCLC samples were assessed using Protein Pathway Array (PPA). The differentially expressed proteins were further confirmed using a tissue microarray (TMA) containing 94 NSCLC samples and were correlated with clinical data and survival. Results: Twelve of 108 proteins (p-CREB(Ser133), p-ERK1/2(Thr202/Tyr204), Cyclin B1, p-PDK1(Ser241), CDK4, CDK2, HSP90, CDC2p34, beta-catenin, EGFR, XIAP and PCNA) were selected to build the predictor to classify normal and tumor samples with 97% accuracy. Five proteins (CDC2p34, HSP90, XIAP, CDK4 and CREB) were confirmed to be differentially expressed between NSCLC (n=94) and benign lung tumor (n=19). Over-expression of CDK4 and HSP90 in tumors correlated with a favorable overall survival in all NSCLC patients and the over-expression of p-CREB(Ser133) and CREB in NSCLC correlated with a favorable survival in smokers and those with squamous cell carcinoma, respectively. Finally, the four proteins (CDK4, HSP90, p-CREB and CREB) were used to calculate the risk score of each individual patient with NSCLC to predict survival. Conclusion: In summary, our data demonstrated a broad disturbance of functionally important regulatory proteins in NSCLC and some of these can be selected as clinically useful biomarkers for diagnosis, classification and prognosis.