Platelets play an important role in tumor growth and, at the same time, platelet characteristics are affected by cancer presence. Therefore, we investigated whether the platelet proteome harbors differentially expressed proteins associated with early-stage cancer. For this proof-of-concept study, patients with early-stage lung (n = 8) or head of pancreas cancer (n = 4) were included, as were healthy sex- and age-matched controls for both subgroups. Blood samples were collected from controls and from patients before surgery. Furthermore, from six of the patients, a second sample was collected two months after surgery. NanoLC-MS/MS-based proteomics of gel-fractionated platelet proteins was used for comparative spectral count analyses of patients to controls and before to after surgery samples. The total platelet proteome dataset included 4384 unique proteins of which 85 were significantly (criteria Fc > 1.5 and p < 0.05) changed in early-stage cancer compared to controls. In addition, the levels of 81 platelet proteins normalized after tumor resection. When filtering for the most discriminatory proteins, we identified seven promising platelet proteins associated with early-stage cancer. In conclusion, this pioneering study on the platelet proteome in cancer patients clearly identifies platelets as a new source of candidate protein biomarkers of early-stage cancer. Biological significance: Currently, most blood-based diagnostics/biomarker research is performed in serum or plasma, while the content of blood cells is usually neglected. It is known that especially blood platelets, which are the main circulating pool of many bioactive proteins, such as growth factors, chemokines, and cytokines, are a potentially rich source of biomarkers. The current study is the first to measure the effect of early-stage cancer on the platelet proteome of patients. Our study demonstrates that the platelet proteome of patients with early-stage lung or head of pancreas cancer differs considerably compared to that of healthy individuals of matched sex and age. In addition, the platelet proteome of cancer patients normalized after surgical resection of the tumor. Exploiting platelet proteome differences linked to both tumor presence and disease status, we were able to demonstrate that the platelet proteome can be mined for potential biomarkers of cancer.