Natural products represent an important source of potential novel antimicrobial drug leads. Low production by microorganisms in cell culture often delays the structural elucidation or even prevents a timely discovery. Starting from the anti-Gram-negative antibacterial compound albicidin produced by Xanthomonas albilineans, we describe a bioactivity-guided approach combined with non-targeted tandem mass spectrometry and spectral (molecular) networking for the discovery of novel antimicrobial compounds. We report eight new natural albicidin derivatives, four of which bear a ß-methoxy cyanoalanine or ß-methoxy asparagine as the central a-amino acid. We present the total synthesis of these albicidins, which facilitated the unambiguous determination of the (2¿S,3¿R)-stereoconfiguration which is complemented by the assessment of the stereochemistry on antibacterial activity.