Solid solution strengthening can play a very important role in the performance of heat resistant steels, not only because of its substantial strengthening effect as such, but also because of the fact that the effect that solid solution strengthening is, by definition, time independent. In the present study a computational alloy design approach is presented to explore the chemical composition of high strength ferritic heat resistant steel designed to have an optimal solid solution strengthening, while minimising the presence of undesirable microstructural components. Alloy compositions covering eleven elements are considered in the calculations. The chemical composition and the associating optimal annealing temperature are optimised simultaneously via a genetic algorithm. To validate the approach, the solid solution strengthening contribution in existing commercial ferritic stainless steel was calculated using the same computational procedures, and it is shown that the documented relative experimental performance of the reference alloys agrees very well with the model predictions. According to the predictions results, the newly designed alloys have a substantially higher solid solution strengthening than found in existing alloys.