Nonulosonic acids, commonly referred to as sialic acids, are a highly important group of nine-carbon sugars common to all domains of life. They all share biosynthetic and structural features, but otherwise display a remarkable chemical diversity. In humans, sialic acids cover all cells which makes them important for processes such as cellular protection, immunity and brain development. On the other hand, sialic acids and other nonulosonic acids have been associated with pathological processes including cancer and viral infections. In prokaryotes, nonulosonic acids are commonly associated with pathogens, which developed through molecular mimicry a strategy to circumvent the host's immune response. However, the remarkably large chemical diversity of prokaryotic nonulosonic acids challenges their discovery, and research on molecular characteristics essential for medical applications are often not feasible. Here, we demonstrate a novel, universal large-scale discovery approach that tackles the unmapped diversity of prokaryotic nonulosonic acids. Thereby, we utilize selective chemical labelling combined with a newly established mass spectrometric all-ion-reaction scanning approach to identify nonulosonic acids and other ulosonic acid-like sugars. In doing so, we provide a first molecular-level comparative study on the frequency and diversity across different phyla. We not only illustrate their surprisingly wide-spread occurrence in non-pathogenic species, but also provide evidence of potential higher carbon variants. Many biomedical studies rely on synthetic routes for sialic acids, which are highly demanding and often of low product yields. Our approach enables large-scale exploration for alternative sources of these highly important compounds.