For (CoCrFeMn)100-xAlx high-entropy alloys, we investigate the phase evolution with increasing Al content (0≤x≤20 at.%). From first-principles theory, aluminum doping drives the alloy structurally from fcc to bcc separated by a narrow two-phase region (fcc+bcc), which is well supported by our experiments. Using KKR-CPA electronic-structure calculations, we highlight the effect of Al doping on the formation enthalpy (alloy stability) and electronic dispersion of (CoCrFeMn)100-xAlx alloys. As chemical short-range order indicates the nascent local order, and entropy changes, as well as expected low-temperature ordering behavior, we use KKR-CPA-based thermodynamic linear response to predict the chemical ordering behavior of arbitrary complex solid-solution alloys - an ideal approach for predictive design of high-entropy alloys. The predictions agree with our present experimental findings and other reported ones. © 2019 American Physical Society.