Rhizonin A and B are hepatotoxic cyclopeptides produced by bacterial endosymbionts (Mycetohabitans endofungorum) of the fungus Rhizopus microsporus. Their toxicity critically depends on the presence of 3-furylalanine (Fua) residues, which also occur in pharmaceutically relevant cyclopeptides of the endolide and bingchamide families. The biosynthesis and incorporation of Fua by non-ribosomal peptide synthetases (NRPS), however, has remained elusive. By genome sequencing and gene inactivation we elucidated the gene cluster responsible for rhizonin biosynthesis. A suite of isotope labeling experiments identified tyrosine and l-DOPA as Fua precursors and provided the first mechanistic insights. Bioinformatics, mutational analysis and heterologous reconstitution identified dioxygenase RhzB as necessary and sufficient for Fua formation. RhzB is a novel type of heme-dependent aromatic oxygenases (HDAO) that enabled the discovery of the bingchamide biosynthesis gene cluster through genome mining.