A theory-guided computational approach for alloy design is presented. Aimed at optimising the desired properties, the microstructure is designed and an alloy composition optimised accordingly, combining criteria based on thermodynamic, thermokinetic and mechanical principles. A genetic algorithm is employed as the optimisation scheme. The approach is applied to the design of ultra-high strength stainless steels. Three composition scenarios, utilising different strengthening precipitates (carbides, Cu and NiAl/Ni₃Ti), are followed. The results are compared to a variety of existing commercial high-end engineering steels, showing that the design strategy presented here may lead to significant improvements in strength beyond current levels.