We have investigated pressure-induced structural transitions in NaBH4 through density-functional theory calculations combined with X-ray and neutron diffraction experiments. Our calculations confirm that the cubic phase is stable up to 5.4 GPa and an orthorhombic phase occurs above 8.9 GPa, as observed in X-ray diffraction experiments. Both the calculations and X-ray diffraction measurements identify an intermediate tetragonal phase that appears between 6 and 8 GPa; that is, between the cubic and orthorhombic phases. This result is also confirmed by high-pressure neutron diffraction experiments performed on NaBD4. Our calculations and X-ray diffraction measurements show that the space group of the orthorhombic phase above 8.9 GPa is Pnma and the orthorhombic phase remains stable up to 30 GPa. The calculated equations of state are in excellent agreement with experiments.