The rational discovery of new specialized metabolites by genome mining represents a very promising strategy in the quest for new bioactive molecules. Ribosomally synthesized and post-translationally modified peptides (RiPPs) are a major class of natural product that derive from genetically encoded precursor peptides. However, RiPP gene clusters are particularly refractory to reliable bioinformatic predictions due to the absence of a common biosynthetic feature across all pathways. Here, we describe RiPPER, a new tool for the family-independent identification of RiPP precursor peptides and apply this methodology to search for novel thioamidated RiPPs in Actinobacteria. Until now, thioamidation was believed to be a rare post-translational modification, which is catalyzed by a pair of proteins (YcaO and TfuA) in Archaea. In Actinobacteria, the thioviridamide-like molecules are a family of cytotoxic RiPPs that feature multiple thioamides, which are proposed to be introduced by YcaO-TfuA proteins. Using RiPPER, we show that previously undescribed RiPP gene clusters encoding YcaO and TfuA proteins are widespread in Actinobacteria and encode a highly diverse landscape of precursor peptides that are predicted to make thioamidated RiPPs. To illustrate this strategy, we describe the first rational discovery of a new structural class of thioamidated natural products, the thiovarsolins from Streptomyces varsoviensis.