Natural evolution relies on the improvement of biological entities by rounds of diversification and selection. In the laboratory, directed evolution has emerged as a powerful tool for the development of new and improved biomolecules, but it is limited by the enormous workload and cost of screening sufficiently large combinatorial libraries. Here we describe the production of gel-shell beads (GSBs) with the help of a microfluidic device. These hydrogel beads are surrounded with a polyelectrolyte shell that encloses an enzyme, its encoding DNA and the fluorescent reaction product. Active clones in these man-made compartments can be identified readily by fluorescence-activated sorting at rates >107 GSBs per hour. We use this system to perform the directed evolution of a phosphotriesterase (a bioremediation catalyst) caged in GSBs and isolate a 20-fold faster mutant in less than one hour. We thus establish a practically undemanding method for ultrahigh-throughput screening that results in functional hybrid composites endowed with evolvable protein components.