The engineered de novo vanillin biosynthesis pathway constructed in Escherichia coli is industrially relevant but limited by the reaction catalyzed by catechol O-methyltransferase, which is intended to catalyze the conversion of protocatechuate to vanillate. To identify alternative O-methyltransferases, we constructed a vanillate sensor based on the Caulobacter crescentus VanR-VanO system. Using an E. coli promoter library, we achieved greater than 14-fold dynamic range in our best rationally constructed sensor. We found that this construct and an evolved variant demonstrate remarkable substrate selectivity, exhibiting no detectable response to the regioisomer byproduct isovanillate and minimal response to structurally similar pathway intermediates. We then harnessed the evolved biosensor to conduct rapid bioprospecting of natural catechol O-methyltransferases and identified three previously uncharacterized but active O-methyltransferases. Collectively, these efforts enrich our knowledge of how biosensing can aid metabolic engineering and constitute the foundation for future improvements in vanillin pathway productivity.