Background: Enzyme activity is at the center of all biological processes. When these activities are misregulated by changes in sequence, expression, or activity, pathologies emerge. Misregulation of protease enzymes such as Matrix Metalloproteinases and Cathepsins play a key role in the pathophysiology of cancer. We describe here a novel class of graphene-based, cost effective biosensors that can detect altered protease activation in a blood sample from early stage lung cancer patients. Methods: The Gene Expression Omnibus (GEO) tool was used to identify proteases differentially expressed in lung cancer and matched normal tissue. Biosensors were assembled on a graphene backbone annotated with one of a panel of fluorescently tagged peptides. The graphene quenches fluorescence until the peptide is either cleaved by active proteases or altered by post-translational modification. 19 protease biosensors were evaluated on 431 commercially collected serum samples from non-lung cancer controls (69%) and pathologically confirmed lung cancer cases (31%) tested over two independent cohorts. Serum was incubated with each of the 19 biosensors and enzyme activity was measured indirectly as a continuous variable by a fluorescence plate reader. Analysis was performed using Emerge, a proprietary predictive and classification modeling system based on massively parallel evolving “Turing machine” algorithms. Each analysis stratified allocation into training and testing sets, and reserved an out-of-sample validation set for reporting. Results: 256 clinical samples were initially evaluated including 35% cancer cases evenly distributed across stages I (29%), II (26%), III (24%) and IV (21%). The case controls included common co-morbidies in the at-risk population such as COPD, chronic bronchitis, and benign nodules (19%). Using the Emerge classification analysis, biosensor biomarkers alone (no clinical factors) demonstrated Sensitivity (Se.) = 92% (CI 82%-99%) and Specificity (Sp.) = 82% (CI 69%-91%) in the out-of-sample set. An independent cohort of 175 clinical cases (age 67±8, 52% male) focused on early detection (26% cancer, 70% Stage I, 30% Stage II/III) were similarly evaluated. Classification showed Se. = 100% (CI 79%-100%) and Sp. = 93% (CI 80%-99%) in the out-of-sample set. For the entire dataset of 175 samples, Se. = 100% (CI 92%-100%) and Sp. = 97% (CI 92%-99%) was observed. Conclusions: Lung cancer can be treated if it is diagnosed when still localized. Despite clear data showing screening for lung cancer by Low Dose Computed Tomography (LDCT) is effective, screening compliance remains very low. Protease biosensors provide a cost effective additional specialized tool with high sensitivity and specificity in detection of early stage lung cancer. A large prospective trial of at-risk smokers with follow up is being conducted to evaluate a commercial version of this assay.