The nucleotide signaling molecule 3',5'-cyclic adenosine monophosphate (3',5'-cAMP) plays important physiological roles, ranging from carbon catabolite repression in bacteria to mediating the action of hormones in higher eukaryotes, including human. However, it remains unclear whether 3',5'-cAMP is universally present in the Firmicutes group of bacteria. We hypothesized that searching for proteins that bind 3',5'-cAMP might provide new insight into this question. Accordingly, we performed a genome-wide screen, and identified the essential Staphylococcus aureus tRNA m1G37 methyltransferase enzyme TrmD, which is conserved in all three domains of life, as a tight 3',5'-cAMP binding protein. TrmD enzymes are known to use S-adenosyl-L-methionine (AdoMet) as substrate; we shown that 3',5'-cAMP binds competitively with AdoMet to the S. aureus TrmD protein, indicating an overlapping binding site. However, the physiological relevance of this discovery remained unclear, as we were unable to identify a functional adenylate cyclase in S. aureus and only detected 2',3'-cAMP but not 3',5'-cAMP in cellular extracts. Interestingly, TrmD proteins from Escherichia coli and Mycobacterium tuberculosis, organisms known to synthesize 3',5'-cAMP, did not bind this signaling nucleotide. Comparative bioinformatics, mutagenesis and biochemical analyses revealed that the highly conserved Tyr86 residue in E. coli TrmD is essential to discriminate between 3',5'-cAMP and the native substrate AdoMet. Combined with a phylogenetic analysis, these results suggest that amino acids in the substrate binding pocket of TrmD underwent an adaptive evolution to accommodate the emergence of adenylate cyclases and thus the signaling molecule 3',5'-cAMP. Altogether this further indicates that S. aureus does not produce 3',5'-cAMP, which would otherwise competitively inhibit an essential enzyme.