The choice of cathode material in Li-ion batteries (LIBs) underpins their overall performance. Discovering new cathode materials is a slow process, and all major commercial cathode materials are still based on those identified in the 1990s. Materials discovery using high-throughput calculations has attracted great research interest, however, reliance on databases of existing materials begs the question of whether these approaches are applicable for finding truly novel materials. In this work, we demonstrate that ab-initio random structure searching (AIRSS), a first-principles structure prediction methods that does not rely on any pre-existing data, can locate low energy structures of complex cathode materials efficiently based only on chemical composition. We use AIRSS to explore three Fe- containing polyanion compounds as low-cost cathodes. Using known quaternary LiFePO4 and quinary LiFeSO4F cathodes as examples, we easily reproduce the known polymorphs, in addition to predicting other, hitherto unknown, low energy polymorphs, and even finding a new polymorph of LiFeSO4F which is more stable than the known ones. We then explore the phase space for Fe-containing fluoroxalates, predicting a range of redox-active phases that have yet to be experimentally synthesized, demonstrating the suitability of AIRSS as a tool for accelerating the discovery of novel cathode materials.