All-solid-state Na-ion batteries that operate at or close to room temperature are a promising next-generation battery technology with enhanced safety and reduced manufacturing cost. An indispensable component of this technology is the solid-state electrolyte that allows rapid shuttling of the mobile cation (i.e., Na+) between the cathode and anode. However, there are very few fast Na-ion conductors with ionic conductivity approaching that of the liquid counterparts (i.e., 1 mS cm-1). In this work, we present the synthesis and characterization of a fast Na-ion conductor, cubic Na3PSe4. This material possesses a room-temperature ionic conductivity exceeding 0.1 mS cm-1 and does not require high-temperature sintering to minimize grain boundary resistance, making it a promising solid-state electrolyte candidate for all-solid-state Na-ion battery applications. On the basis of density functional theory, nudged elastic band, and molecular dynamics investigations, we demonstrate that the framework of cubic Na3PSe4 only permits rapid Na+ diffusion with the presence of defects, and that the formation of the Na vacancy (charge-balanced by slight Se2- oxidation) is more energetically favorable among the various defects considered. This finding provides important guidelines to further improve Na-ion conductivity in this class of materials.