Ribosomally synthesized and post-translationally modified peptides (RiPPs) form a highly diverse class of natural products, with various biotechnologically and clinically relevant activities. A recent increase in discoveries of novel RiPP classes suggests that currently known RiPPs constitute just the tip of the iceberg. Genome mining has been a driving force behind these discoveries, but remains challenging due to a lack of universal genetic markers for RiPP detection. In this review, we discuss how various genome mining methodologies contribute towards the discovery of novel RiPP classes. Some methods prioritize novel biosynthetic gene clusters (BGCs) based on shared modifications between RiPP classes. Other methods identify RiPP precursors using machine-learning classifiers. The integration of such methods as well as integration with other types of omics data in more comprehensive pipelines could help these tools reach their potential, and keep pushing the boundaries of the chemical diversity of this important class of molecules.