Paclitaxel can exert therapeutic effects by interacting with microtubules. Stathmin and β-III-tubulin, which have impact on microtubule activity, are believed to be involved in the chemotherapy. The purpose of the present study was to evaluate the associations between stathmin and β-III-tubulin expression and treatment response and survivals in patients with non-small cell lung cancer (NSCLC). Two hundred thirty-eight patients who were treated by platinum-based chemotherapy were enrolled in this study, among them, 111 patients also received paclitaxel treatment. Formalin-fixed and paraffin-embedded tumor tissues were collected for messenger RNA (mRNA) and protein detection. We assessed the associations of the two molecules with treatment response and survival outcome. High level of stathmin exhibited poor response to chemotherapy (for mRNA, P = 0.041; for protein, P = 0.017). Overexpression of stathmin was associated with shorter overall survival (for mRNA, P = 0.012; for protein, P = 0.014) and progression-free survival (for mRNA, P = 0.039; for protein, P = 0.022). Of note, this association was only observed in patients who were treated by both platinum and paclitaxel. Similar effects were not observed for β-III-tubulin. The findings demonstrated that paclitaxel effect may be interfered with stathmin; overexpression of stathmin is a predictive marker for a worse prognosis in patients with NSCLC who were treated by both platinum and paclitaxel chemotherapy.