Rationale: Whether histologic subtype of non-small cell lung cancer (NSCLC) has an important effect on prognosis following surgery is unknown. Objectives: We hypothesized that we could predict mortality more effectively by integrating precise tumor size and histology rather than relying on conventional staging. Methods: We used the SEER registry. Inclusion criteria were: 1) primary squamous cell or adenocarcinoma, 2) potentially curative surgery, defined as a lobectomy or bilobectomy, 3) lymph node dissection performed, and 4) pathologic stage IA or IB. Results: From 1988-2000, 7,965 patients were included. For both all cause mortality and lung cancer associated mortality, tumor size demonstrated the strongest association (log-rank p<0.0001 for each). When tumors were small ( 2 cm) lung cancer associated mortality was similar for adenocarcinoma when compared to squamous cell carcinoma. When tumors were 3 cm in size, lung cancer associated mortality was higher for adenocarcinoma. The increased risk of lung cancer associated mortality with adenocarcinoma was more pronounced in those under age 65. Survival prediction using precise size and histology had much better discriminatory power than conventional TNM staging (p=0.005). Conclusion: Staging that takes into account size, histology, late recurrence risk, and patient age is more accurate than the current TNM system and is clinically relevant since improved prediction can facilitate better decisions on the use of adjuvant chemotherapy.