Recent studies described several different routes that facilitate nitrogen-nitrogen bond formation in natural product biosynthesis. We report herein the identification of unprecedented machinery for hydrazine formation involved in the biosynthesis of s56-p1, a dipeptide natural product with a unique hydrazone unit. The gene cassette comprising this machinery is widespread across several bacterial phyla, highlighting the overlooked potential of bacteria to synthesize hydrazine.