The lack of α2-6-linkage specific sialidases limits the structural and functional studies of sialic-acid-containing molecules. Photobacterium damselae α2-6-sialyltransferase (Pd2,6ST) was shown previously to have α2-6-specific, but weak, sialidase activity. Here, we develop a high-throughput blue-white colony screening method to identify Pd2,6ST mutants with improved α2-6-sialidase activity from mutant libraries generated by sequential saturation mutagenesis. A triple mutant (Pd2,6ST S232L/T356S/W361F) has been identified with 100-fold improved activity, high α2-6-sialyl linkage selectivity, and ability to cleave two common sialic acid forms, N-acetylneuraminic acid (Neu5Ac) and N-glycolylneuraminic acid (Neu5Gc). It is a valuable tool for sialoglycan structural analysis and functional characterization. The sequential saturation mutagenesis and screening strategy developed here can be explored to evolve other linkage-specific neoglycosidases from the corresponding glycosyltransferases.