Despite a voluminous literature on potential protein biomarkers and a compelling need for diagnostic tests based on biomarkers to detect cancers at much earlier, more treatable stages, progress has been limited. New methods and new instruments for analysis of differences in gene expression, gene methylation, and proteomics are being employed to try to accelerate the discovery phase. Given the heterogeneity of tumor mechanisms and the limitations of analytical methods, it is likely that a variety of strategies will be needed and will be complementary. That is the basis of this review of proteomic approaches. This article adopts a systems biology view, starting with mRNA transcripts in tumors and cultured tumor cells to detect mRNA overexpression, some of which will be correlated with protein overexpression. Some of those proteins may be secreted or released into proximal biofluids and plasma. Detection of low-abundance tumor proteins in the complex and dynamic mixture that is plasma requires combinations of increasingly powerful technologies. The biological amplification of protein signals through the immune system offers autoantibodies as potential biomarkers. Higher abundance proteins, including acute-phase reactants, may have practical value, especially if the proteins are modified as part of the cancer processes. Low molecular weight proteins, fragments, and peptides may offer complementary biomarkers. Promising biomarker candidates must be confirmed in independent studies. Then they must be submitted to higher-throughput methods practical for large-scale validation studies and, hopefully, for clinical and epidemiological applications. Standardized operating procedures for specimen handling, design and use of various reference standards, care to avoid bias and confounding, and guidelines for reporting findings and contributing datasets should enhance the prospects for predictive proteomic profiling of people at risk for cancers.