Cation-disordered lithium-excess metal oxides have recently emerged as a promising new class of high-energy-density cathode materials for Li-ion batteries, but the exploration of disordered materials has been hampered by their vast and unexplored composition space. This study proposes a practical methodology for the identification of stable cation-disordered rocksalts. Here, it is established that the efficient method, which makes use of special quasirandom structures, correctly predicts cation-ordering strengths in agreement with accurate Monte-Carlo simulations and experimental observations. By applying the approach to the composition space of ternary oxides with formula unit LiA0.5B0.5O2 (A, B: transition metals), this study discovers a previously unknown cation-disordered structure, LiCo0.5Zr0.5O2, that may function as the basis for a new class of cation-disordered cathode materials. This computational prediction is confirmed experimentally by solid-state synthesis and subsequent characterization by powder X-ray diffraction demonstrating the potential of the computational screening of large composition spaces for accelerating materials discovery.