The evaluation of mediastinal lymph nodes is critical for the correct staging of patients with lung cancer (LC). Endobronchial ultrasound-guided transbronchial needle aspiration (EBUS-TBNA) is a minimally invasive technique for mediastinal staging, though unfortunately lymph node micrometastasis is often missed by cytological analysis. The aim of this study was to evaluate the predictive capacity of methylation biomarkers and provide a classification rule for predicting malignancy in false negative EBUS-TBNA samples. The study included 112 patients with a new or suspected diagnosis of LC that were referred to EBUS-TBNA. Methylation of p16/INK4a, MGMT, SHOX2, E-cadherin, DLEC1, and RASSF1A was quantified by nested methylation-specific qPCR in 218 EBUS-TBNA lymph node samples. Cross-validated linear regression models were evaluated to predict malignancy. According to EBUS-TBNA and final diagnosis, 90 samples were true positives for malignancy, 110 were true negatives, and 18 were false negatives. MGMT, SHOX2, and E-cadherin were the methylation markers that better predicted malignancy. The model including sex, age, short axis diameter and standard uptake value of adenopathy, and SHOX2 showed 82.7% cross-validated sensitivity and 82.4% specificity for the detection of malignant lymphadenopathies among negative cytology samples. Our results suggest that the predictive model approach proposed can complement EBUS-TBNA for mediastinal staging.