DNAzymes have been limited in application by their low catalytic rates. Here, we evolved a new peroxidase DNAzyme mSBDZ-X-3 through a directed evolution method based on the capture of self-biotinylated DNA catalyzed by its intrinsic peroxidase activity. The mSBDX-X-3 DNAzyme has a parallel G-quadruplex structure and has more favorable catalytic properties than all previously reported peroxidase DNAzyme variants. We applied mSBDZ-X-3 in an aptamer-coupled proximity-based labeling proteomic assay to determine the proteins that bind to cell surface cancer biomarkers EpCAM and nucleolin. Confocal microscopy, western blot analysis, and LC-MS/MS showed that the hybrid DNAzyme aptamer-coupled proximity assay-labeled proteins associated with EpCAM and nucleolin within 6-12 min in fixed cancer cells. The labeled proteins were identified by mass spectrometry. This study provides a highly efficient peroxidase DNAzyme, a methodology for selection of such variants, and a method for its application in spatial proteomics using entirely nucleic acid-based tooling.