The de novo design of enzymes remains a central challenge, requiring consideration of catalytic mechanism and optimization across biochemical and biophysical criteria. To capture these criteria, we draw on principles from evolutionary biology. Here, we present dEVA (design by EVolutionary Algorithm), a multi-objective design framework for structure-based protein design. We apply dEVA to the zero-shot, de novo design of metalloenzymes by optimizing for the coordination sphere of catalytic metals. We fully characterize one of these designs: a bi-zinc metalloenzyme exhibiting promiscuous hydrolytic activity towards both phosphomonoesters and phosphodiesters. This design achieves a catalytic efficiency (k cat /K M ) of up to 1500 M -1 s -1 and a rate enhancement ((k cat /K M )/k w ) of up to 3 x 10 13 , comparable to characterized natural phosphatases. dEVA offers a general and modular strategy for the programmable design of protein function without dependence on natural templates, predefined motif, or evolutionary information.