In an age of whole-genome analysis, the mass spectrometry-based bottom-up strategy is now considered to be the most powerful method for in-depth proteomics analysis. As part of this strategy, highly efficient and complete proteolytic digestion of proteins into peptides is crucial for successful proteome profiling with deep coverage. To achieve this goal, prolonged digestion time and the use of multiple proteases have been adopted. The long digestion time required and tedious sample treatment steps severely limit the sample processing throughput. Though utilization of immobilized protease greatly reduces the digestion time, highly efficient proteolysis of extremely complex proteomic samples remains a challenging task. Here, we propose a dual matrix-based complementary digestion method using two types of immobilized trypsin with opposite matrix hydrophobicity prepared by attaching trypsin on hydrophobic or hydrophilic polymer-brush-modified nanoparticles. The polymer brushes on the nanoparticles serve as three-dimensional supports for a large amount of trypsin immobilization and lead to ultrafast and highly efficient protein digestion. More importantly, the two types of immobilized trypsin show high complementarity in protein digestion with only ∼60% overlap in peptide identification for yeast and membrane protein of mouse liver. Complementary digestion by applying these two types of immobilized trypsin together leads to obviously enhanced protein and peptide identification. Furthermore, the dual matrix-based complementary digestion shows particular advantage in the digestion of membrane proteins, as twice the number of identified peptides is obtained compared with solution digestion using free proteases, demonstrating its potential as a promising alternative to promote proteomics analysis with higher protein sequence coverage.