Sulfatases are a highly conserved family of enzymes found in all three domains of life. To be active, sulfatases undergo a unique post-translational modification leading to the conversion of either a critical cysteine ("Cys-type" sulfatases) or a serine ("Ser-type" sulfatases) into a Calpha-formylglycine (FGly). This conversion depends on a strictly conserved sequence called "sulfatase signature" (C/S)XPXR. In a search for new enzymes from the human microbiota, we identified the first sulfatase from Firmicutes. Matrix-assisted laser desorption ionization time-of-flight analysis revealed that this enzyme undergoes conversion of its critical cysteine residue into FGly, even though it has a modified (C/S)XAXR sulfatase signature. Examination of the bacterial and archaeal genomes sequenced to date has identified many genes bearing this new motif, suggesting that the definition of the sulfatase signature should be expanded. Furthermore, we have also identified a new Cys-type sulfatase-maturating enzyme that catalyzes the conversion of cysteine into FGly, in anaerobic conditions, whereas the only enzyme reported so far to be able to catalyze this reaction is oxygen-dependent. The new enzyme belongs to the radical S-adenosyl-l-methionine enzyme superfamily and is related to the Ser-type sulfatase-maturating enzymes. This finding leads to the definition of a new enzyme family of sulfatase-maturating enzymes that we have named anSME (anaerobic sulfatase-maturating enzyme). This family includes enzymes able to maturate Cys-type as well as Ser-type sulfatases in anaerobic conditions. In conclusion, our results lead to a new scheme for the biochemistry of sulfatases maturation and suggest that the number of genes and bacterial species encoding sulfatase enzymes is currently underestimated.