High-entropy alloys (HEAs), although often presumed to be random solid solutions, have recently been shown to display nanometer-scale variations in the arrangements of their multiple chemical elements. Here, we study the effects of this compositional heterogeneity in HEAs on their mechanical properties using in situ compression testing in the transmission electron microscope (TEM), combined with molecular dynamics simulations. We report an anomalous size effect on the yield strength in HEAs, arising from such compositional heterogeneity. By progressively reducing the sample size, HEAs initially display the classical "smaller-is-stronger" phenomenon, similar to pure metals and conventional alloys. However, as the sample size is decreased below a critical characteristic length (~180 nm), influenced by the size-scale of compositional heterogeneity, a transition from homogeneous deformation to a heterogeneous distribution of planar slip is observed, coupled with an anomalous "smaller-is-weaker" size effect. Atomic-scale computational modeling shows these observations arise due to compositional fluctuations over a few nanometers. These results demonstrate the efficacy of influencing mechanical properties in HEAs through control of local compositional variations at the nanoscale.