A new quaternary hydride, NaBaPdH3, has been synthesized. The novel structure type was refined, in the hexagonal space group P6(3)/mmc, from single-crystal X-ray data complemented by neutron powder diffraction data from the corresponding deuteride. The unit cell dimensions at 150 K were determined to be a = 6.049(1) Angstrom and c = 6.061(3) Angstrom. The structure consists of trigonal planar PdH3 complex anions, with formally zerovalent palladium, in a framework of sodium and barium counterions. It is related to the CaCuP structure, with the PdH3 unit at the P atom site and Ba and Na at the Cu and Ca atom sites, respectively.