The de novo design of enzymes remains a central challenge, requiring consideration of catalytic mechanism and optimization across biochemical and biophysical criteria. Here we present dEVA (design by EVolutionary Algorithm), a multi-objective protein design framework built on principles drawn from evolutionary biology. We apply dEVA to the zero-shot, de novo design of metalloenzymes by optimizing the coordination sphere of catalytic metals. We characterize a bizinc metalloenzyme that exhibits promiscuous hydrolytic activity towards both phosphomonoesters and phosphodiesters. This design achieves a rate enhancement ((k cat /K M )/k w ) up to 3 × 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 or evolutionary information.