The increasing coverage and sensitivity of LC-MS/MS-based proteomics have expanded its applications in systems medicine. In particular, label-free quantitation approaches are enabling biomarker discovery in terms of statistical comparison of proteomic profiles across large numbers of clinical samples. However, it still remains poorly understood how much protein markers can add novel insights compared to markers derived from mRNA transcriptomic profiling. Using paired label-free LC-MS/MS and gene expression microarray measurements from primary samples of patients with acute myeloid leukemia (AML), we demonstrate here that while the quantitative proteomic and transcriptomic profiles were highly correlated, in general, the marker panels showing statistically significant expression changes across the disease and healthy groups were profoundly different between protein and mRNA levels. In particular, the proteomic assay enabled unique links to known leukemic processes, which were missed when using the transcriptomic profiling alone, as well as identified additional links to metabolic regulators and chromatin remodelers, such as GPX1, fumarate hydratase, and SET oncogene, which have subsequently been evaluated in independent AML samples. Overall, these results highlighted the complementary and informative view obtained from the quantitative LC-MS/MS approach into the AML deregulated signaling networks.