All-solid-state batteries based on non-combustible solid electrolytes are promising candidates for safe energy storage systems. In addition, they offer the opportunity to utilize metallic lithium as an anode. However, it has proven to be a challenge to design an electrolyte that combines high ionic conductivity and processability with thermodynamic stability toward lithium. Herein, we report a new highly conducting solid solution that offers a route to overcome these challenges. The Li-P-S ternary was first explored via a combination of high-throughput crystal structure predictions and solid-state synthesis (via ball milling) of the most promising compositions, specifically, phases within the Li3P-Li2S tie line. We systematically characterized the structural properties and Li-ion mobility of the resulting materials by X-ray and neutron diffraction, solid-state nuclear magnetic resonance spectroscopy (relaxometry), and electrochemical impedance spectroscopy. A Li3P-Li2S metastable solid solution was identified, with the phases adopting the fluorite (Li2S) structure with P substituting for S and the extra Li+ ions occupying the octahedral voids and contributing to the ionic transport. The analysis of the experimental data is supported by extensive quantum-chemical calculations of both structural stability, diffusivity, and activation barriers for Li+ transport. The new solid electrolytes show Li-ion conductivities in the range of established materials, while their composition guarantees thermodynamic stability toward lithium metal anodes.