Thermostable variants of the Class II fructose bisphosphate aldolase have been isolated following four rounds of directed evolution using DNA shuffling of the fda genes from Escherichia coli and Edwardsiella ictaluri. Variants from all four generations of evolution have been purified and characterized. The variants show increased thermostability with no loss of catalytic function at room temperature. The temperature at which 50% of the initial enzyme activity is lost after incubation for 10 min (T50) of the most stable variant, 4-43D6, is increased by 11-12 degrees C over the wild-type enzymes and the half-life of activity at 53 degrees C is increased approximately 190-fold. In addition, variant 4-43D6 shows increased stability to treatment with organic solvents. DNA sequencing of the evolved variants has identified the mutations which have been introduced and which lead to increased thermostability, and the role of the mutations introduced is discussed.