High Entropy Alloys (HEAs) are a new broad class of near-random solid solution alloys that can possess some impressive mechanical and physical properties including high stability against grain growth (i.e. low grain boundary (GB) mobility). Here, it is shown that an initially flat GB in an HEA can become spontaneously rough, driven by natural local compositional fluctuations. Roughening lowers the total GB energy and thus can inhibit migration. A parameter-free theoretical framework is developed to demonstrate the energetics and size scales of the roughening in terms of solute/GB interaction energies and GB disconnection energies. Above a critical level of solute/GB interactions, a planar GB is predicted to roughen down to the scale of the GB periodic unit. A similar theory for 1D GBs (minimum periodic length in one direction) is also developed since such geometries are common in atomistic simulations. Specific predictions are made for the [100] symmetric tilt boundaries E17[100](530) and E5[100](310) in a model CoCuFeNi alloy and atomistic simulations demonstrate roughening consistent with the theory. Analysis of the stresses needed to drive migration shows how migration can be inhibited or enhanced, rationalizing variations in mobility of GBs in HEAs. (c) 2022 The Author(s). Published by Elsevier Ltd on behalf of Acta Materialia Inc. This is an open access article under the CC BY-NC-ND license ( http://creativecommons.org/licenses/by-nc-nd/4.0/ )