With the goal of improving performance of a hydrogen-rich storage medium, the influence of a collection of first and second period transition metal fluorides on the destabilization of NaBH4 is studied on samples produced by ball milling NaBH4 with 2 mol% of a metal fluoride additive. The effects obtained by increasing additive amount and changing oxidation state are also evaluated for NbF5, CeF3, and CeF4. The as-milled products are characterized by in-house power X-ray diffraction, while the hydrogen release and decomposition are monitored by temperature programmed desorption with residual gas analysis, differential scanning calorimetry, and thermogravimetry. The screening of samples containing 2 mol% of additive shows that distinctive groups of transition metal fluorides affect the ball milling process differently depending on their enthalpy of formation, melting point, or their ability to react at the temperatures achieved during ball milling. This leads to the formation of NaBF4 in the case of TiF4, MnF3, VF4, CdF2, NbF5, AgF, and CeF3 and the presence of the metal in CrF3, CuF2, and AgF. There is no linear correlation between the position of the transition metal in the periodic table and the observed behavior. The thermal behavior of the products after milling is given by the remaining NaBH4, fluoride, and the formation of intermediate metastable compounds. A noticeable decrease of the decomposition temperature is seen for the majority of the products, with the exceptions of the samples containing YF3, AgF, and CeF3. The largest decrease of the decomposition temperature is observed for NbF5. When comparing increasing amounts of the same additive, the largest decrease of the decomposition temperature is observed for 10 mol% of NbF5. Higher amounts of additive result in the loss of the NaBH4 thermal signal and ultimately the loss of the crystalline borohydride. When comparing additives with the same transition metal and different oxidation states, the most efficient additive is found to be the one with a higher oxidation state. Furthermore, among all the samples studied, higher oxidation state metal fluorides are found to be the most destabilizing agents for NaBH4. Overall, the present study shows that there is no single parameter affecting the destabilization of NaBH4 by transition metal fluorides. Instead, parameters such as the transition metal electronegativity and oxidation state or the enthalpy of formation of the fluoride and its melting point are competing to influence the destabilization. In particular, it is found that the combination of a high metal oxidation state and a low fluoride melting point will enhance destabilization. This is observed for MnF3, NbF5, NiF2, and CuF2, which lead to high gas releases from the decomposition of NaBH4 at the lowest decomposition temperatures.