An efficient β-fucosidase was evolved by DNA shuffling from the Escherichia coli lacZ β-galactosidase. Seven rounds of DNA shuffling and colony screening on chromogenic fucose substrates were performed, using 10,000 colonies per round. Compared with native β-galactosidase, the evolved enzyme purified from cells from the final round showed a 1,000-fold increased substrate specificity for o-nitrophenyl fucopyranoside versus o-nitrophenyl galactopyranoside and a 300-fold increased substrate specificity for p-nitrophenyl fucopyranoside versus p-nitrophenyl galactopyranoside. The evolved cell line showed a 66-fold increase in p-nitrophenyl fucosidase specific activity. The evolved fucosidase has a 10- to 20-fold increased k_cat/K_m for the fucose substrates compared with the native enzyme. The DNA sequence of the evolved fucosidase gene showed 13 base changes, resulting in six amino acid changes from the native enzyme. This effort shows that the library size that is required to obtain significant enhancements in specificity and activity by reiterative DNA shuffling and screening, even for an enzyme of 109 kDa, is within range of existing high-throughput technology. Reiterative generation of libraries and stepwise accumulation of improvements based on addition of beneficial mutations appears to be a promising alternative to rational design.