BACKGROUND The purpose of this study is to evaluate the significance of histology as a predictor of recurrence after resection in patients with early-stage non-small cell lung cancer. METHODS A total of 1,870 consecutive patients in stage I and II with adenocarcinoma or squamous cell carcinoma (SCC) who underwent complete tumor resection with systematic lymph node dissection between August 1992 and December 2007 were included. RESULTS In patients with SCC, significantly more tumors were stage IB or higher. Ever smokers were more common in patients with SCC, and more patients with SCC died of other diseases. In stage IA, a statistically significant difference in the 5-year recurrence-free probability was observed between adenocarcinoma and SCC (91.4% and 82.6%, respectively; P < .001), whereas no such difference was observed in stage IB (74.4% and 73.6%, respectively; P = .934). In stage II, the 5-year recurrence-free probability for adenocarcinoma was significantly lower than that for SCC (47% and 73%, respectively; P < .001). In stage IA, patients with predominantly bronchioloalveolar carcinoma subtype were more common compared with stage IB or higher in patients with adenocarcinoma. CONCLUSIONS It is important to offset the prognostic impact of comorbidities associated with cigarette smoking because more patients with SCC died of other diseases. When evaluating its significance as a predictor of recurrence stratified by stage, histology showed a different impact on postoperative recurrence within different substages. Histologic subtype distribution was different among substages in patients with adenocarcinoma. Disease stages should be considered while evaluating histology as a predictor of recurrence.