Solid electrolyte with stable and fast Na ionic conductivity is of central importance in the development of all-solid-state sodium batteries. Here we present a novel Na conductor based on complex hydrides with composition of NaNHBH. It exhibits remarkable thermal stability up to 593 K and excellent electrochemical stable window up to 10 V (vs. Na/Na). It demonstrates a high Na conductivity of 1.0 × 10 S cm at a temperature of 372 K, which is much higher than those of its precursors NaNH and NaBH. All-solid-state Na-ion batteries were constructed by employing the obtained NaNHBH as electrolyte, TiS as cathode and sodium foil as anode, which can reversibly discharge/charge for over 200 cycles with more than 50% capacity retention at temperature of 353 K and a rate of 0.1 C. This work opens the gate to develop advanced solid electrolytes via combination of metal amides with closo borates.