The HLA molecules are membrane-bound transporters that carry peptides from the cytoplasm to the cell surface for surveillance by circulating T lymphocytes. Although low levels of soluble HLA molecules (sHLA) are normally released into the blood, many types of tumor cells release larger amounts of these sHLA molecules, presumably to counter immune surveillance by T cells. Here we demonstrate that these sHLA molecules are still bound with their authentic peptide repertoires, similar to those of the membranal HLA molecules (mHLA). Therefore, a single immunoaffinity purification of the plasma sHLA molecules, starting with a few milliliters of patients' blood, allows for identification of very large sHLA peptidomes by mass spectrometry, forming a foundation for development of a simple and universal blood-based cancer diagnosis. The new methodology was validated using plasma and tumor cells of multiple-myeloma and leukemia patients, plasma of healthy controls, and with cultured cancer cells. The analyses identified thousands of sHLA peptides, including some cancer-related peptides, present among the sHLA peptidomes of the cancer patients. Furthermore, because the HLA peptides are the degradation products of the cellular proteins, this sHLA peptidomics approach opens the way for investigation of the patterns of protein synthesis and degradation within the tumor cells.