The use of biological catalysts for industrial scale synthetic chemistry is highly attractive, given their cost effectiveness, high specificity that obviates the need for protecting group chemistry, and the environmentally benign nature of enzymatic procedures. Here we evolve the naturally occurring 2-keto-3-deoxy-6-phosphogluconate (KDPG) aldolases from Thermatoga maritima and Escherichia coli, into enzymes that recognize a nonfunctionalized electrophilic substrate, 2-keto-4-hydroxyoctonoate (KHO). Using an in vivo selection based on pyruvate auxotrophy, mutations were identified that lower the K(M) value up to 100-fold in E. coli KDPG aldolase, and that enhance the efficiency of retro-aldol cleavage of KHO by increasing the value of k(cat)/K(M) up to 25-fold in T. maritima KDPG aldolase. These data indicate that numerous mutations distal from the active site contribute to enhanced 'uniform binding' of the substrates, which is the first step in the evolution of novel catalytic activity.