The yield strength of random metal alloys, i.e. alloys with random occupation of the crystalline lattice sites by the elemental constituent atoms all considered as solutes, is primarily understood as controlled by solute/dislocation interactions. Solute-solute interactions exist and provide the energetic driving force for both short-range and long-range order but can then also affect yield strength even in the random alloy. Here, a recent theory for random alloys is extended to include solute-solute interactions described by pair-wise interactions. The new theory involves the standard deviation in total solute-solute interaction energies as a dislocation segment glides through the material, which changes specific solute-solute pairs across the glide plane at every pair distance. An analytic expression is derived for the above standard deviation and validated against numerical simulations on a wide range of model random alloys consisting of 2-5 elements interacting via Lennard-Jones pair potentials. The theory is applied to the bcc MoNbTaW high entropy alloy, using solute-solute interactions computed via first-principles, and a model NbTaV alloy, described by EAM potentials, where the strength increases negligibly by 2% and 0.45%, respectively. Application to random dilute fcc Ni-Al, where the first-neighbor Al-Al interaction is very strongly repulsive, shows significant strengthening of 60-100% at 10% Al, depending on the origin of the inputs. Some connections to literature atomistic simulations on Ni-Al are also presented. Overall, the present theory provides a quantitative framework for assessing the relative roles of solute-dislocation and solute-solute interactions on strengthening in random alloys. (C) 2020 Acta Materialia Inc. Published by Elsevier Ltd. All rights reserved.