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 C-formylglycine (FGly). This conversion depends on a strictly conserved sequence called “sulfatase signature”: C/SxPxR. In a search for new enzymes from the human microbiota, we identified the first sulfatase from Firmicutes. MALDI-TOF analysis reveals that this enzyme undergoes conversion of its critical cysteine residue into FGly, eventhough it has a modified C/SxAxR sulfatase signature. Examination of the bacterial and archae 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 SAM 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 Enzymes). 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.