To investigate how formally low-valent transition-metal hydride complexes are stabilized without the conventional "back-donation mechanism" of electron density to ligand orbitals, a new tetrahedral formally zerovalent-palladium hydride complex has been synthesized and structurally characterized in Sr2PdH4 and Ba2PdH4. The two isomorphous hydrides were synthesized by hot sintering of the binary alkaline-earth hydride with palladium powder at temperatures close to 750 degrees C. The structures were determined to be of beta-K2SO4 type by means of X-ray single-crystal diffraction complemented by neutron powder diffraction from the corresponding deuteride. The structure can be described as consisting of tetrahedral palladium hydride complexes and alkaline earth counterions. But the hydrides are also not far from being of an interstitial type, with hydrogen slightly off-center toward palladium from the octahedral interstices coordinating one palladium and five alkaline-earth atoms. This intermediate character is reflected in long Pd-H distances in the complex, averaging 1.80 Angstrom in Ba2PdH4 and 1.78 Angstrom in Sr2PdH4. It also emphasizes the importance of the counterion contribution to the stabilization of these unusual, formally low oxidation states.