We have identified a highly conserved RNA motif located upstream of genes encoding molybdate transporters, molybdenum cofactor (Moco) biosynthesis enzymes, and proteins that utilize Moco as a coenzyme. Bioinformatics searches have identified 176 representatives in gamma-Proteobacteria, delta-Proteobacteria, Clostridia, Actinobacteria, Deinococcus-Thermus species and DNAs from environmental samples. Using genetic assays, we demonstrate that a Moco RNA in Escherichia coli associated with the Moco biosynthetic operon controls gene expression in response to Moco production. In addition, we provide evidence indicating that this conserved RNA discriminates against closely related analogues of Moco. These results, together with extensive phylogenetic conservation and typical gene control structures near some examples, indicate that representatives of this structured RNA represent a novel class of riboswitches that sense Moco. Furthermore, we identify variants of this RNA that are likely to be triggered by the related tungsten cofactor (Tuco), which carries tungsten in place of molybdenum as the metal constituent.