Objectives Endobronchial ultrasound-guided transbronchial needle aspiration (EBUS-TBNA) is becoming the preferred method of mediastinal staging for lung cancer. We investigated the learning curve for EBUS-TBNA using risk-adjusted cumulative sum (Cusum). Methods A retrospective study of EBUS-TBNA was performed at a single academic institution for patients with mediastinal or hilar lymphadenopathy in the setting of proven or suspected lung cancer. A sampling pass was defined as a full retraction and repositioning of the aspiration needle. Rapid on-site evaluation was not available. To track proficiency, risk-adjusted Cusum analysis was performed using acceptable and unacceptable failure rates of 10% and 20%, respectively. Failure was defined as false negative or nondiagnostic results. Results During the study period, 231 patients underwent EBUS-TBNA. Prevalence of mediastinal or hilar malignancy was 66.7% (154 out of 231). Sensitivity was 92.2% (142 out of 154), and negative predictive value was 87.9% (58 out of 66). Node size was identified as a significant predictor of EBUS-TBNA success by multiple regression. Risk-adjusted Cusum analysis demonstrated that the first and only unacceptable decision interval was crossed at 22 cases. Individual practitioner learning curves were highly variable, and the operator with the highest volume was the most consistently proficient. Conclusions In our experience, attainment of an acceptable failure rate for EBUS-TBNA required 22 cases. Node size is a predictor of EBUS-TBNA success. Risk-adjusted Cusum proved a powerful evaluative tool to monitor the training process of this new procedure.