Development of functional inorganic and transition metal compounds is usually based on ad hoc qualified guesses, with computational methods playing a lesser role than in drug discovery. A de novo evolutionary algorithm (EA) is presented that automatically generates transition metal complexes using a search space constrained around chemically meaningful structures assembled from three kinds of fragments: a part shared by all structures and typically containing the metal center itself, one or several parts consisting of ligand skeletons, and unconstrained parts that may grow and vary freely. In EA optimizations, using a cost-efficient fitness function based on a linear quantitative structure-activity relationship model for catalytic activity, we demonstrate the capabilities of the method by retracing the transition from the first-generation, phosphine-based Grubbs olefin metathesis catalysts to second-generation catalysts containing N-heterocyclic carbene ligands instead of phosphines. Moreover, DFT calculations on selected high-fitness, last-generation structures from these evolutionary experiments suggest that, in terms of catalytic activity, the structures arrived at by virtual evolution alone compare favorably with existing, highly active catalysts. The structures from the evolution experiments are, however, complex and probably difficult to synthesize, but a set of manually simplified variations thereof might form the leads for a new generation of Grubbs catalysts.