Cathode materials that have high specific energies and low manufacturing costs are vital for the scaling up of lithium-ion batteries (LIBs) as energy storage solutions. Fe-based intercalation cathodes are highly attractive because of the low-cost and the abundance of the raw materials. However, existing Fe-based materials, such as LiFePO4 suffer from low capacity due to the large size of the polyanions. Turning to mixed anion systems can be a promising strategy to achieve higher specific capacity. Recently, anti-perovskite structured oxysulphide Li2FeSO has been synthesised and reported to be electrochemically active. In this work, we perform an extensive computational search for iron-based oxysulphides using ab initio random structure searching (AIRSS). By performing an unbiased sampling of the Li-Fe-S-O chemical space, several new oxysulphide phases have been discovered which are predicted to be less than 50 meV/atom from the convex hull and potentially accessible for synthesis. Among the predicted phases, two anti-Ruddlesden-Popper structured materials Li2Fe2S2O and Li4Fe3S3O2 have been found to be attractive as they have high theoretical capacities with calculated average voltages 2.9 V and 2.5 V respectively. With band gaps as low as about 2.0 eV, they are expected to exhibit good electronic conductivities. By performing nudged-elastic band calculations, we show that the Li-ion transport in these materials takes place by hopping between the nearest neighbouring sites with low activation barriers between 0.3 eV and 0.5 eV. The richness of new materials yet to be synthesised in the Li-Fe-S-O phase field illustrate the great opportunity in these mixed anion systems for energy storage applications and beyond. The dataset includes the structure searching results and outputs of further property calculations. The analysis codes are also included as Jupyter Notebooks. Also hosted on GitHub. Preprint hosted on ChemRxiv.