Purpose: To identify the optimal strategy for staging the mediastinum of patients with known non-small-cell lung cancer (NSCLC), stratified by tumor (T) classification. Methods: We used a decision-analytic model to compare the health outcomes and cost-effectiveness of three staging strategies: (1) chest computed tomography alone, (2) selective mediastinoscopy, and (3) routine mediastinoscopy. The overall effectiveness and cost of each strategy was a function of the proportion of patients accurately staged and the risks, benefits, and costs of the diagnostic tests and treatments used. Probability estimates and costs were derived from primary data and the literature. We adopted a societal perspective and calculated incremental cost-effectiveness ratios (ICERs) as cost per quality-adjusted life year (QALY) gained. Results: Both mediastinoscopy strategies correctly identified more patients with mediastinal involvement (N2/N3 disease) and assigned them to multimodal regimens. Routine mediastinoscopy maximized quality-adjusted life expectancy in all patients, irrespective of T classification, and this result was robust to varying the model estimates over their reported ranges. In T1 patients, selective mediastinoscopy cost $24,500 per QALY gained, compared with $78,800 per QALY gained for routine mediastinoscopy. In T2 and T3 patients, the ICER of routine mediastinoscopy was more favorable ($42,800 and $53,400 per QALY gained, respectively). Conclusion: Routine mediastinoscopy maximizes quality-adjusted life expectancy in patients with known NSCLC, and its ICER compares favorably with other currently accepted medical technologies. The suvival benefit and cost-effectiveness of this strategy are greater in patients with T2 and T3 tumors and are likely to improve with advances in multimodal therapy.