A theory to predict the initial flow stress of an arbitrary N-component fcc random alloy is extended to predict the additional strengthening when a dilute concentration of a substitutional element is introduced. Assuming properties for the N-component alloy to be established, the theory requires only information on the elastic and lattice constants of the new N + 1-alloy, and makes a parameter-free prediction for the strength increment due to the added N + 1st element. The theory is applied to the CoCrFeNiAlx and CoCrFeNiMnAlx systems, achieving good agreement with experiments. The theory thus serves as a valuable tool for guiding design of new fcc random alloys. (C) 2017 Acta Materialia Inc. Published by Elsevier Ltd. All rights reserved.