Large-scale protein sequencing methods rely on enzymatic digestion of complex protein mixtures to generate a collection of peptides for mass spectrometric analysis. Here we examine the use of multiple proteases (trypsin, LysC, ArgC, AspN, and GluC) to improve both protein identification and characterization in the model organism Saccharomyces cerevisiae. Using a data-dependent, decision tree-based algorithm to tailor MS(2) fragmentation method to peptide precursor, we identified 92 095 unique peptides (609 665 total) mapping to 3908 proteins at a 1% false discovery rate (FDR). These results were a significant improvement upon data from a single protease digest (trypsin) - 27 822 unique peptides corresponding to 3313 proteins. The additional 595 protein identifications were mainly from those at low abundances (i.e., < 1000 copies/cell); sequence coverage for these proteins was likewise improved nearly 3-fold. We demonstrate that large portions of the proteome are simply inaccessible following digestion with a single protease and that multiple proteases, rather than technical replicates, provide a direct route to increase both protein identifications and proteome sequence coverage.