Recently, high-entropy alloys (HEAs) have attracted wide attention due to their extraordinary materials properties. A main challenge in identifying new HEAs is the lack of efficient approaches for exploring their huge compositional space. Ab initio calculations have emerged as a powerful approach that complements experiment. However, for multicomponent alloys existing approaches suffer from the chemical complexity involved. In this work we propose a method for studying HEAs computationally. Our approach is based on the application of machine-learning potentials based on ab initio data in combination with Monte Carlo simulations. The high efficiency and performance of the approach are demonstrated on the prototype bcc NbMoTaW HEA. The approach is employed to study phase stability, phase transitions, and chemical short-range order. The importance of including local relaxation effects is revealed: they significantly stabilize single-phase formation of bcc NbMoTaW down to room temperature. Finally, a so-far unknown mechanism that drives chemical order due to atomic relaxation at ambient temperatures is discovered.