The production of two new heterocyclic peptide isomers, catenulobactins A (1) and B (2), in cultures of Catenuloplanes sp. RD067331 was significantly increased when it was cocultured with a mycolic acid-containing bacterium. The planar structures and absolute configurations of the catenulobactins were determined based on NMR/MS and chiral-phase GC-MS analyses. Catenulobactin B (2) displayed Fe(III)-chelating activity and moderate cytotoxicity against P388 murine leukemia cells.