We give a general condition for a discrete spin system with nearest-neighbor interactions on the $\mathbb{Z}^d$ lattice to exhibit long-range order. The condition is applicable to systems with residual entropy in which the long-range order is entropically driven. As a main example we consider the antiferromagnetic $q$-state Potts model and rigorously prove the existence of a broken sub-lattice symmetry phase at low temperature and high dimension -- a new result for $q\ge 4$. As further examples, we prove the existence of an ordered phase in a clock model with hard constraints and extend the known regime of the demixed phase in the lattice Widom-Rowlinson model.