Genome mining and chemical analyses revealed that rhizosphere bacteria (Paraburkholderia graminis) produce a new type of siderophore, gramibactin, a lipodepsipeptide that efficiently binds iron with a logβ value of 27.6. Complexation-induced proton NMR chemical shifts show that the unusual N-nitrosohydroxylamine (diazeniumdiolate) moieties participate in metal binding. Gramibactin biosynthesis genes are conserved in numerous plant-associated bacteria associated with rice, wheat, and maize, which may utilize iron from the complex.