Formation, stability and properties of new metal borohydrides within RE(BH4)3-NaBH4, RE = Ce, Pr, Er or Gd is investigated. Three new bimetallic sodium rare-earth borohydrides, NaCe(BH4)4, NaPr(BH4)4 and NaEr(BH4)4 are formed based on an addition reaction between NaBH4 and halide free rare-earth metal borohydrides RE(BH4)3, RE = Ce, Pr, Er. All the new compounds crystallize in the orthorhombic crystal system. NaCe(BH4)4 has unit cell parameters of a = 6.8028(5), b = 17.5181(13), c = 7.2841(5) Å and space group Pbcn. NaPr(BH4)4 is isostructural to NaCe(BH4)4 with unit cell parameters of a = 6.7617(2), b = 17.4678(7), c = 7.2522(3) Å. NaEr(BH4)4 crystallizes in space group Cmcm with unit cell parameters of a = 8.5379(2), b = 12.1570(4), c = 9.1652(3) Å. The structural relationships, also to the known RE(BH4)3, are discussed in detail and related to the stability and synthesis conditions. Heat treatment of NaBH4-Gd(BH4)3 mixture forms an unstable amorphous phase, which decomposes after one day at RT. NaCe(BH4)4 and NaPr(BH4)4 show reversible hydrogen storage capacity of 1.65 and 1.04 wt% in the fourth H2 release, whereas that of NaEr(BH4)4 continuously decreases. This is mainly assigned to formation of metal hydrides and possibly slower formation of sodium borohydride. The dehydrogenated state clearly contains rare-earth metal borides, which stabilize boron in the dehydrogenated state.