A computational approach to design a new grade of precipitation hardened Ultra-High Strength (UHS) stainless steel is presented wherein genetic approaches are combined with thermodynamic computations. The composition scenarios are designed and optimized in order to obtain higher yield strength than the existing commercial counterparts by promoting the formation of desirable microstructures and suppressing the undesirable ones. The strength target is approached by forming a fine lath martensitic matrix and optimizing the number of nanoprecipitates (MX carbide, NiAl, Ni₃Ti and Cu) particles based on thermokinetic theories. Corrosion resistance is accounted for by ensuring a minimum Cr content of 12 wt% in the matrix as precipitation has taken place. Four alloys are computationally designed which are strengthened by either MC carbides, Cu particles, Ni rich intermetallics, or a combination of all of them, considering 13 alloying elements (Al, C, Co, Cr, Cu, Mn, Mo, N, Nb, Ni, Si, Ti, V). The composition optimization is performed by allowing each element to potentially take 32 compositions in the given ranges which leads to a solution space containing 10²⁰ options. The enormous computational effort is drastically reduced by applying the genetic optimization algorithm. The results of the analysis are compared to other computationally more expensive approaches (combinatorial and iterative optimization algorithms) obtaining similar results. The model predictions are also compared to a variety of existing commercial high-end engineering steels, showing that the design strategy presented here may potentially lead to significant improvements in strength.