Through first-principles calculations and crystal structure prediction techniques, we identify a new layered oxysulfide LiAlSO in orthorhombic structure as a novel lithium superionic conductor. Two kinds of stacking sequences of layers of AlS_{2}O_{2} are found in different temperature ranges. Phonon and molecular dynamics simulations verify their dynamic stabilities, and wide band gaps up to 5.6 eV are found by electronic structure calculations. The lithium migration energy barrier simulations reveal the collective interstitial-host ion "kick-off" hopping mode with barriers lower than 50 meV as the dominating conduction mechanism for LiAlSO, indicating it to be a promising solid-state electrolyte in lithium secondary batteries with fast ionic conductivity and a wide electrochemical window. This is a first attempt in which the lithium superionic conductors are designed by the crystal structure prediction method and may help explore other mixed-anion battery materials.