Analyses of microbial genome sequences reveal numerous examples of gene clusters encoding proteins typically involved in complex natural product biosynthesis but not associated with the production of known natural products. In Streptomyces coelicolor M145 there are several gene clusters encoding new nonribosomal peptide synthetase (NRPS) systems not associated with known metabolites. Application of structure-based models for substrate recognition by NRPS adenylation domains predicts the amino acids incorporated into the putative peptide products of these systems, but the accuracy of these predictions is untested. Here we report the isolation and structure determination of the new tris-hydroxamate tetrapeptide iron chelator coelichelin from S. coelicolor using a genome mining approach guided by substrate predictions for the trimodular NRPS CchH, and we show that this enzyme, which lacks a C-terminal thioesterase domain, together with a homolog of enterobactin esterase (CchJ), are required for coelichelin biosynthesis. These results demonstrate that accurate prediction of adenylation domain substrate selectivity is possible and raise intriguing mechanistic questions regarding the assembly of a tetrapeptide by a trimodular NRPS.