Cathodes are critical components of rechargeable batteries. Conventionally, the search for cathode materials relies on experimental trial-and-error and a traversing of existing computational/experimental databases. While these methods have led to the discovery of several commercially viable cathode materials, the chemical space explored so far is limited and many phases will have been overlooked, in particular, those that are metastable. We describe a computational framework for battery cathode exploration based on ab initio random structure searching (AIRSS), an approach that samples local minima on the potential energy surface to identify new crystal structures. We show that by delimiting the search space using a number of constraints, including chemically aware minimum interatomic separations, cell volumes, and space group symmetries, AIRSS can efficiently predict both thermodynamically stable and metastable cathode materials. Specifically, we investigate LiCoO2, LiFePO4, and LixCuyFz to demonstrate the efficiency of the method by rediscovering the known crystal structures of these cathode materials. The effect of parameters, such as minimum separations and symmetries, on the efficiency of the sampling is discussed in detail. The adaptation of the minimum interatomic distances on a species-pair basis, from low-energy optimized structures to efficiently capture the local coordination environment of atoms, is explored. A family of novel cathode materials based on the transition-metal oxalates is proposed. They demonstrate superb energy density, oxygen-redox stability, and lithium diffusion properties. This article serves both as an introduction to the computational framework and as a guide to battery cathode material discovery using AIRSS.