All-solid-state lithium batteries (ASSLBs) are promising for safety and high-energy-density large-scale energy storage. In this contribution, we propose a Li3–4xZrxPS4 (LZPS) by Zr-doped β-Li3PS4 (LPS) as a novel solid electrolyte (SE) for ASSLBs based on experimental and simulation methods. The structure, electronic property, mechanical property, and ionic transport properties of LZPS (x = 0, 0.03, 0.06, and 0.1) are investigated with first-principles calculations. Meanwhile, LZPS is prepared by solid states reaction method. By combining experimental analysis and first-principles calculations, it is confirmed that a small amount of Zr4+ can be successfully doped into the framework of β-LPS composites without significantly compromising structural integrity. When the Zr4+ concentration is x = 0.03, the doped material Li2.88Zr0.03PS4 exhibits the highest ionic conductivity (5.1 × 10−4 S·cm−1) at 30 °C, and the Li-ion migration energy barrier is the lowest. The Li2.88Zr0.03PS4 SE has obtained the best mechanical properties, the good ductility, and shear deformation resistance, which can better maintain the structural stability of the battery. In addition, the Li/Li symmetrical cell is assembled, which shows excellent electrochemical stability of electrolyte against lithium. The constructed all-solid-state batteries (LiCoO2-Li6PS5Cl|Li2.88Zr0.03PS4|Li-In) delivers an initial discharge capacity of 130.4 mAh·g−1 at 0.2 C and a capacity retention of 85.1% after 100 cycles at room temperature. This study provides a promising electrolyte for the application of ASSLBs with high ionic conductivity and excellent stability against lithium.