All-solid-state sodium-ion batteries are promising candidates for large-scale energy storage applications. The key enabler for an all-solid-state architecture is a sodium solid electrolyte that exhibits high Na(+) conductivity at ambient temperatures, as well as excellent phase and electrochemical stability. In this work, we present a first-principles-guided discovery and synthesis of a novel Cl-doped tetragonal Na3PS4 (t-Na3-xPS4-xClx) solid electrolyte with a room-temperature Na(+) conductivity exceeding 1 mS cm(-1). We demonstrate that an all-solid-state TiS2/t-Na3-xPS4-xClx/Na cell utilizing this solid electrolyte can be cycled at room-temperature at a rate of C/10 with a capacity of about 80 mAh g(-1) over 10 cycles. We provide evidence from density functional theory calculations that this excellent electrochemical performance is not only due to the high Na(+) conductivity of the solid electrolyte, but also due to the effect that "salting" Na3PS4 has on the formation of an electronically insulating, ionically conducting solid electrolyte interphase.