Precipitation hardening and solid-solution strengthening (SSS) are the most effective strengthening mechanisms in creep-resistant, corrosion-resistant ferritic/martensitic steels. However, it is difficult to achieve a simultaneous maximization of both mechanisms as alloying elements may affect both mechanisms in a different way and upset considerations based on one strengthening mechanism only. To address this challenge, a generic alloy-by-design model was developed. The model uses quantitative descriptions for both the time-dependent precipitate population and its resulting strengthening contribution and the time-independent SSS due to chemical elements remaining in solid solution. Furthermore, the model involves full thermodynamic calculations at appropriate temperatures. The formulations were found to capture the contributions of both strengthening mechanisms in existing Cr containing martensitic steel grades rather precisely. Subsequently, the model was used to probe new steel compositions in the compositional domain of 9–12% Cr martensitic creep-resistant steels containing nine other alloying elements, each at different concentration levels. A genetic algorithm was used to probe the compositional search domain. The calculations were performed assuming a continuous operating temperature of 650 °C and a lifetime of at least 105 h. Alloy compositions and heat treatment conditions leading to too large amounts of undesirable phases and other detrimental effects were automatically rejected. A Pareto front linking the strength contributions according to precipitation hardening or SSS was constructed by combining results of two separate optimization routes. From the Pareto front analysis, steel compositions with optimized combinations of strengthening mechanisms were identified. The robustness of the new solutions was tested by enforcing concentration variations as encountered in industrial practice and to test for abrupt changes in predicted creep strength values. The newly designed steel is predicted to significantly outperform existing commercial creep-resistant martensitic steel grades and has a target composition such that the usual deviations in elemental concentration levels do not significantly affect the final creep strength.