These findings beg the question: are there other oxysulphides waiting to be discovered? Computational materials discovery, and in particular, high-throughput screening studies, have previously been applied to many fields including battery cathodes . Those studies, however, rely heavily on existing experimental data, as hypothetical materials are constructed from simple substitutions of the known materials . For lithium iron oxysulphides, which remain largely unexplored so far, the available experimental data are scarce. The other way of discovering new materials is to directly search for low energy structures using firstprinciples calculations, with little or no experimental inputs . Finding the lowest energy crystal structure is a challenging task, as it requires global optimisation over the high-dimensional configuration space. Many approaches have been developed to tackle the problem, including basin hopping , minima hopping , genetic algorithms and particle-swarm optimisation . In this work, we explore the lithium iron oxysulphide chemical space using ab initio random structure searching (AIRSS), which is a simple, efficient and highly parallel method for searching for low energy structures. By sampling the Li-Fe-S-O space in an unbiased way, we have discovered many previously unknown phases that are both predicted to be relatively stable and have good electrochemical performances for cathode applications. Among those phases, two anti-Ruddlesden-Popper structured materials Li 2 Fe 2 S 2 O and Li 4 Fe 3 S 3 O 2 are particularly attractive due to them being both nearly on the convex hull and have theoretical capacities exceeding that of the Li 2 FeSO. Subsequent DFT calculations using the predicted crystal structures show that they have average voltages of 2.9 V and 2.5 V respectively, and band gaps about 2.0 eV. Using the climbing-image nudged elastic band method , we show that both of them contains Li-diffusion networks with low transition state barriers similar to Li 2 FeSO.