Engineering catalytic and biophysical properties of enzymes is an essential step en route to advanced biomedical and industrial applications. Here, we developed a high-throughput screening and directed evolution strategy relying on single-cell hydrogel encapsulation to enhance the performance of D-Amino acid oxidase from Rhodotorula gracilis (RgDAAOx), a candidate enzyme for cancer therapy. We used a cascade reaction between RgDAAOx variants surface displayed on yeast and horseradish peroxidase (HRP) in the bulk media to trigger enzyme-mediated crosslinking of phenol-bearing fluorescent alginate macromonomers, resulting in hydrogel formation around single yeast cells. The fluorescent hydrogel capsules served as an artificial phenotype and basis for pooled library screening by fluorescence activated cell sorting (FACS). We screened a RgDAAOx variant library containing ∼106 clones while lowering the D-Ala substrate concentration over three sorting rounds in order to isolate variants with low Km. After three rounds of FACS sorting and regrowth, we isolated and fully characterized four variants displayed on the yeast surface. We identified variants with a more than 5-fold lower Km than the parent sequence, with an apparent increase in substrate binding affinity. The mutations we identified were scattered across the RgDAAOx structure, demonstrating the difficulty in rationally predicting allosteric sites and highlighting the advantages of scalable library screening technologies for evolving catalytic enzymes.