The botulinum neurotoxin serotype A (BoNT/A) cuts a single peptide bond in SNAP25, an activity used to treat a wide range of diseases. Reengineering the substrate specificity of BoNT/A's protease domain (LC/A) could expand its therapeutic applications; however, LC/A's extended substrate recognition (≈ 60 residues) challenges conventional approaches. We report a directed evolution method for retargeting LC/A and retaining its exquisite specificity. The resultant eight-mutation LC/A (omLC/A) has improved cleavage specificity and catalytic efficiency (1300- and 120-fold, respectively) for SNAP23 versus SNAP25 compared to a previously reported LC/A variant. Importantly, the BoNT/A holotoxin equipped with omLC/A retains its ability to form full-length holotoxin, infiltrate neurons, and cleave SNAP23. The identification of substrate control loops outside BoNT/A's active site could guide the design of improved BoNT proteases and inhibitors.