Blood-based approaches to detect early-stage cancer provide an opportunity to improve survival rates for lung cancer, the most lethal cancer world-wide. Multiple approaches for blood-based cancer detection using molecular analytes derived from individual 'omics (cell-free DNA, RNA transcripts, proteins, metabolites) have been developed and tested, generally showing significantly lower sensitivity for early-stage versus late-stage cancer. We hypothesized that an approach using multiple types of molecular analytes, including broad and untargeted coverage of proteins, could identify biomarkers that more directly reveal changes in gene expression and molecular phenotype in response to carcinogenesis to potentially improve detection of early-stage lung cancer. To that end, we designed and conducted one of the largest multi-omics, observational studies to date, enrolling 2,513 case and control subjects. Multi-omics profiling detected 113,671 peptides corresponding to 8,385 protein groups, 219,729 RNA transcripts, 71,756 RNA introns, and 1,801 metabolites across all subject samples. We then developed a machine learning-based classifier for lung cancer detection comprising 682 of these multi-omics analytes. This multi-omics classifier demonstrated 89%, 80%, and 98-100% sensitivity for all-stage, stage I, and stage III-IV lung cancer, respectively, at 89% specificity in a validation set. The application of a multi-omics platform for discovery of blood-based disease biomarkers, including proteins and complementary molecular analytes, enables the noninvasive detection of early-stage lung cancer with the potential for downstaging at initial diagnosis and the improvement of clinical outcomes.