There is strong interest in creating an enzyme that can deacylate natural cephalosporins such as cephalosporin C in order to efficiently acquire the starting compound for the industrial production of semisynthetic cephalosporin antibiotics. In this study, the active site of the glutaryl acylase from Pseudomonas SY-77 was randomized rationally. Several mutations that were found in previous studies to enhance the activity of the enzyme towards adipyl-7-aminodesacetoxycephalosporanic acid (ADCA) and cephalosporin C have now been combined, and libraries have been made in which random amino acid substitutions at these positions are joined. The mutants were expressed in a leucine-deficient Escherichia coli strain and subjected to growth selection with adipyl-leucine or amino-adipyl-leucine as sole leucine source. The mutants growing on these media were selected and purified, and their hydrolysis activities towards adipyl-7-ADCA and cephalosporin C were tested. Several mutants with highly improved activities towards the desired substrates were found in these rationally randomized libraries. The best mutant was selected from a library of totally randomized residues: 178, 266, and 375. This mutant comprises two mutations, Y178F + F375H, which synergistically improve the catalytic efficiency towards adipyl-7-ADCA 36-fold. The activity of this mutant towards adipyl-7-ADCA is 50% of the activity of the wild-type enzyme towards the preferred substrate glutaryl-7-aminocephalosporanic acid, and therefore the characteristics of this mutant approach those needed for industrial application.