Mediastinal staging of non-small-cell lung cancer (NSCLC) is of paramount importance. It distinguishes operable from inoperable disease, guides prognosis and allows accurate comparison of outcomes in clinical trials. Noninvasive imaging modalities for mediastinal staging include CT, PET and integrated PET-CT. Mediastinoscopy is considered the current gold standard; however, each of these techniques has limitations in sensitivity or specificity. These inadequacies mean that 10% of operations performed with curative intent in patients with NSCLC are futile, owing to inaccurate locoregional lymph-node staging. Endoscopic and endobronchial ultrasound-guided mediastinal lymph-node aspiration are important and promising innovative techniques with reported sensitivities and specificities higher than standard investigations. The role of these techniques in mediastinal lymph-node staging is evolving rapidly and early data suggest that they may diminish the need for invasive surgical staging of the mediastinum. Furthermore, these are outpatient procedures that do not require general anesthesia and may be combined safely in the same sitting, for optimal accuracy of mediastinal staging. We propose a new algorithm for the diagnosis and staging of NSCLC, based on the current evidence, which incorporates endoscopic and endobronchial ultrasound as a first investigation after CT in patients with intrathoracic disease.