While evidence for lung cancer screening implementation in Europe is awaited, Rapid Diagnostic Units have been established in many hospitals to accelerate the early diagnosis of lung cancer. We seek to develop an algorithm to detect lung cancer in a symptomatic population attending such unit, based on a sensitive serum marker panel. Serum concentrations of Epidermal Growth Factor, sCD26, Calprotectin, Matrix Metalloproteinases -1, -7, -9, CEA and CYFRA 21.1 were determined in 140 patients with respiratory symptoms (lung cancer and controls with/without benign pathology). Logistic Lasso regression was performed to derive a lung cancer prediction model, and the resulting algorithm was tested in a validation set. A classification rule based on EGF, sCD26, Calprotectin and CEA was established, able to reasonably discriminate lung cancer with 97% sensitivity and 43% specificity in the training set, and 91.7% sensitivity and 45.4% specificity in the validation set. Overall, the panel identified with high sensitivity stage I non-small cell lung cancer (94.7%) and 100% small-cell lung cancers. Our study provides a sensitive 4-marker classification algorithm for lung cancer detection to aid in the management of suspicious lung cancer patients in the context of Rapid Diagnostic Units.