Background Oral cancer survival rates increase significantly when it is detected and treated early. Unfortunately, clinicians now lack tests which easily and reliably distinguish pre-malignant oral lesions from those already transitioned to malignancy. A test for proteins, ones found in non-invasively-collected whole saliva and whose abundances distinguish these lesion types, would meet this critical need. Methodology/Principal Findings To discover such proteins, in a first-of-its-kind study we used advanced mass spectrometry-based quantitative proteomics analysis of the pooled soluble fraction of whole saliva from four subjects with pre-malignant lesions and four with malignant lesions. We prioritized candidate biomarkers via bioinformatics and validated selected proteins by western blotting. Bioinformatic analysis of differentially abundant proteins and initial western blotting revealed increased abundance of myosin and actin in patients with malignant lesions. We validated those results by additional western blotting of individual whole saliva samples from twelve other subjects with pre-malignant oral lesions and twelve with malignant oral lesions. Sensitivity/specificity values for distinguishing between different lesion types were 100%/75% (p = 0.002) for actin, and 67%/83% (p<0.00001) for myosin in soluble saliva. Exfoliated epithelial cells from subjects' saliva also showed increased myosin and actin abundance in those with malignant lesions, linking our observations in soluble saliva to abundance differences between pre-malignant and malignant cells. Conclusions/Significance Salivary actin and myosin abundances distinguish oral lesion types with sensitivity and specificity rivaling other non-invasive oral cancer tests. Our findings provide a promising starting point for the development of non-invasive and inexpensive salivary tests to reliably detect oral cancer early.