High entropy alloys (HEA) represent a class of materials with promising properties, such as high strength and ductility, radiation damage tolerance, etc. At the same time, a combinatorially large variety of compositions and a complex structure render them quite hard to study using conventional methods. In this work, we present a computationally efficient methodology based on ab initio calculations within the coherent potential approximation. To make the methodology predictive, we apply an exchange-correlation correction to the equation of state and take into account thermal effects on the magnetic state and the equilibrium volume. The approach shows good agreement with available experimental data on bulk properties of solid solutions. As a particular case, the workflow is applied to a series of iron-group HEA to investigate their solid solution strengthening within a parameter-free model based on the effective medium representation of an alloy. The results reveal intricate interactions between alloy components, which we analyze by means of a simple model of local bonding. Thanks to its computational efficiency, the methodology can be used as a basis for an adaptive learning workflow for optimal design of HEA.