The epidermal growth factor receptor (EGFR) is overexpressed in the majority of non-small cell lung cancers (NSCLC). EGFR tyrosine kinase inhibitors, such as gefitinib and erlotinib, produce 9% to 27% response rates in NSCLC patients. E-Cadherin, a calcium-dependent adhesion molecule, plays an important role in NSCLC prognosis and progression, and interacts with EGFR. The zinc finger transcriptional repressor, ZEB1, inhibits E-cadherin expression by recruiting histone deacetylases (HDAC). We identified a significant correlation between sensitivity to gefitinib and expression of E-cadherin, and ZEB1, suggesting their predictive value for responsiveness to EGFR-tyrosine kinase inhibitors. E-Cadherin transfection into a gefitinib-resistant line increased its sensitivity to gefitinib. Pretreating resistant cell lines with the HDAC inhibitor, MS-275, induced E-cadherin along with EGFR and led to a growth-inhibitory and apoptotic effect of gefitinib similar to that in gefitinib-sensitive NSCLC cell lines including those harboring EGFR mutations. Thus, combined HDAC inhibitor and gefitinib treatment represents a novel pharmacologic strategy for overcoming resistance to EGFR inhibitors in patients with lung cancer.