Selenium is an essential micronutrient, but its presence in biology has been limited to protein and nucleic acid biopolymers. The recent identification of the first biosynthetic pathway for selenium-containing small molecules suggests that there is a larger family of selenometabolites that remains to be discovered. Using a bioinformatic search strategy that relies on mapping of composite active site motifs, we identify a recently evolved branch of abundant and uncharacterized metalloenzymes that we predict are involved in selenometabolite biosynthesis. Biochemical studies confirm this prediction and show that these enzymes form an unusual C-Se bond onto histidine, thus giving rise to a novel selenometabolite and potent antioxidant that we have termed ovoselenol. Aside from providing insights into the evolution of this enzyme class and the structural basis of C-Se bond formation, our work offers a blueprint for charting the microbial selenometabolome in the future.