Aryl-O-demethylation is a common rate-limiting step in the catabolism of lignin-related compounds, including guaiacol. Here we used randomly barcoded transposon insertion sequencing (RB-TnSeq) in the bacterium Novosphingobium aromaticivorans to identify a Rieske-type guaiacol O-demethylase, GdmA. Similarity searches identified GdmA homologs in other bacteria, along with candidate reductase partners, denoted GdmB. GdmAB combinations were biochemically characterized for activity with several lignin-related substrates. Structural and sequence comparisons of vanillate- and guaiacol-specific O-demethylase active sites revealed conserved hallmarks of substrate specificity. GdmAB combinations were also evaluated in Pseudomonas putida KT2440, which does not natively utilize guaiacol. GdmAB from Cupriavidus necator N-1 demonstrated the highest rate of guaiacol turnover in vitro and in engineered P. putida strains and notably higher catalytic efficiency than a cytochrome P450 system (GcoAB) and the vanillate Rieske-type O-demethylase from P. putida (VanAB). The GdmAB O-demethylases described here expand the suite of options for microbial conversion of a model lignin-derived substrate.