The opportunistic pathogen Pseudomonas aeruginosa, one of the most prevalent species in infections of the cystic fibrosis lung, produces a range of secondary metabolites, among them the respiratory toxin 2-heptyl-1-hydroxyquinolin-4(1H)-one (2-heptyl-4-hydroxyquinoline N-oxide, HQNO). Cultures of the emerging cystic fibrosis pathogen Mycobacteroides abscessus detoxify HQNO by methylating the N-hydroxy moiety. In this study, the class I methyltransferase MAB_2834c and its orthologue from Mycobacterium tuberculosis, Rv0560c, were identified as HQNO O-methyltransferases. The P. aeruginosa exoproducts 4-hydroxyquinolin-2(1H)-one (DHQ), 2-heptylquinolin-4(1H)-one (HHQ), and 2-heptyl-3-hydroxyquinolin-4(1H)-one (the ‘Pseudomonas quinolone signal’, PQS), some structurally related (iso)quinolones, and the flavonol quercetin were also methylated; however, HQNO was by far the preferred substrate. Both enzymes converted a benzimidazole[1,2-a]pyridine-4-carbonitrile-based compound, representing the scaffold of antimycobacterial substances, to an N-methylated derivative. We suggest that these promiscuous methyltransferases, newly termed as heterocyclic toxin methyltransferases (Htm), are involved in cellular response to chemical stress and possibly contribute to resistance of mycobacteria toward antimicrobial natural compounds as well as drugs. Thus, synthetic antimycobacterial agents may be designed to be unamenable to methyl transfer.