Vibrio anguillarum is a bacterial pathogen that causes serious damage to aquatic fish, and its rapid detection and prevention are critical. DNAzymes are DNA-based catalysts with excellent stability. In this study, in vitro selection of DNAzymes was performed using the crude extracellular matrix (CEM) of V. Anguillarum as the target. Different from previous selections targeting bacterial CEM, this work used an unmodified DNA library, allowing easier adoption of the technology. After seven rounds of selection, a DNAzyme named VAE-2 with high activity and specificity was obtained. It showed the highest activity toward V. Anguillarum among eight types of tested bacterial strains. Polyvalent metal ions are needed for its activity. Protease treatment of the CEM and filtration studies indicated that the target is a protein with a molecular weight between 50 k and 100 k Da. A fluorescent biosensor was designed for V. anguillarum with a detection limit down to 4000 cfu/mL, and detection was demonstrated for real fish tissue and feeding water samples. Being the first work of DNAzyme-based sensing of aquatic bacteria, this study indicates that unmodified DNA can be used for targeting bacterial CEM, and it provides a new framework for developing other RNA-cleaving DNAzymes for rapid detection of pathogenic bacteria and water pollution.