All-solid-state sodium-ion batteries (ASIBs) are promising candidates for large-scale energy storage applications. To build such a battery system, efficient solid-state electrolytes (SSEs) with high sodium ionic conductivity at room temperature and good electrochemical stability as well as interface compatibility are required. In this work, using density functional theory combined with molecular dynamics simulation and a phase diagram, we have studied the potential of yttrium halide-based materials (Na3YX6, where X = Cl or Br) with inherent cation vacancies as diffusion carriers for solid electrolytes in ASIBs. A great balance between electrochemical stability and ionic conductivity found in these two systems overcomes the shortcomings of sulfide- and oxide-based SSEs. In particular, these two materials show Na+ conductivities of 0.77 and 0.44 mS cm-1 at 300 K and wide electrochemical windows of 0.51-3.75 and 0.57-3.36 V, and good interfacial stability with Na metal anode and high-potential polyanion (fluoro)phosphate cathode materials, respectively. These features make halide-based materials promising efficient solid-state electrolytes for Na-ion batteries.