Batteries based on a fluoride shuttle (Fluoride Ion Battery, FIB) can theoretically provide high energy densities and can thus be considered as an interesting alternative to Li-ion batteries. Large improvements are still needed regarding their actual performance, in particular for the ionic conductivity of the solid electrolyte. At the current state of the art, two types of fluoride families can be considered for electrolyte applications: alkaline-earth fluorides having a fluorite-type structure and rare-earth fluorides having a tysonite-type structure. As regard to the latter, high ionic conductivities have been reported for doped LaF3 single crystals. However, polycrystalline materials would be easier to implement in a FIB due to practical reasons in the cell manufacturing. Hence, we have analyzed in detail the ionic conductivity of La1-yBayF3-y (0≤y≤0.15) solid solutions prepared by ball milling. The combination of DC and AC conductivity analyses provides a better understanding of the conduction mechanism in tysonite-type fluorides with a blocking effect of the grain boundaries. Heat treatment of the electrolyte material was performed and leads to an improvement of the ionic conductivity. This confirms the detrimental effect of grain boundaries and opens new route for the development of solid electrolytes for FIB with high ionic conductivities.