High Entropy Alloys (HEAs) are a new class of random alloys having impressive strength and toughness. Here, a mechanistic, parameter-free, and predictive theory for the temperature-, composition-, and strain-rate-dependence of the plastic yield strength of fcc HEAs is presented, validated, and applied to understand recent experiments. To first order, each elemental component in the HEA is considered as a solute embedded in the effective matrix of the surrounding alloy. Strengthening is then mainly achieved due to dislocation interactions with the random local concentration fluctuations around the average composition. The theory is validated against molecular simulations on model Fe-Ni-Cr alloys. Hall-Petch-corrected yield strengths in Ni-Co-Fe-Cr-Mn fcc HEM are then predicted using only available experimental information, and good quantitative agreement is achieved. The theory demonstrates the origins of the high strength and detailed trends with composition, materials parameters, temperature, thus identifying the key measurable/calculable material properties needed for design and optimization of fcc HEAs, and is a general model for fcc random alloys. (C) 2016 Acta Materialia Inc. Published by Elsevier Ltd. All rights reserved.