We present an analysis of temperature-dependent atomic short-range ordering and phase stability of the face-centered cubic CrCoNi medium-entropy alloy employing a combination of ab initio calculations and on-lattice machine learning interatomic potentials. Temperature-dependent properties are studied with canonical Monte Carlo simulations. At around 975 K a phase transition into an ordered Cr(Ni,Co)2 phase (MoPt2-type) is found. This hitherto not reported state has an ordering energy twice as large than the ordered structures previously suggested. We show that magnetism is not responsible for the observed chemical ordering.