Adenylation domains CcbC and LmbC control the specific incorporation of amino acid precursors in the biosynthesis of lincosamide antibiotics celesticetin and lincomycin. Both proteins originate from a common L-proline-specific ancestor, but LmbC was evolutionary adapted to use an unusual substrate, (2S,4R)-4-propyl-proline (PPL). Using site-directed mutagenesis of the LmbC substrate binding pocket and an ATP-[32P]PPi exchange assay, three residues, G308, A207 and L246, were identified as crucial for the PPL activation, presumably forming together a channel of a proper size, shape and hydrophobicity to accommodate the propyl side chain of PPL. Subsequently, we experimentally simulated the molecular evolution leading from L-proline-specific substrate binding pocket to the PPL-specific LmbC. The mere change of three amino acid residues in originally strictly L-proline-specific CcbC switched its substrate specificity to prefer PPL and even synthetic alkyl-L-proline derivatives with prolonged side chain. This is the first time that such a comparative study provided an evidence of the evolutionary relevant adaptation of the adenylation domain substrate binding pocket to a new sterically different substrate by a few point mutations. The herein experimentally simulated rearrangement of the substrate binding pocket seems to be the general principle of the de novo genesis of adenylation domains' unusual substrate specificities. However, to keep the overall natural catalytic efficiency of the enzyme, a more comprehensive rearrangement of the whole protein would probably be employed within natural evolution process.