All-solid-state fluoride shuttle batteries (FSBs) present endless possibilities for next-generation rechargeable batteries. However, no standard choice for solid electrolytes and electrodes in FSBs has been established to date. Additionally, details of how F ions travel through the working device are yet to be fully understood. Here, we studied the electrochemical properties of tysonite Ce0.95A0.05F2.95 (A = Ca, Sr, and Ba) and Ce0.95Mg0.05F2.95 (actually, a composite of CeF3 and MgF2) solid electrolytes, and their crystal structures using neutron diffraction data. In particular, Ce0.95Ca0.05F2.95 exhibited the highest electrical conductivity and the shortest bond between F ions. Furthermore, F-vacancies introduced by the substitution of Ca2+ for Ce3+ were accommodated only at the F1 site. The bond valence sum (BVS) analysis results indicated that there was a significant difference in the BVS values of F ions: BVS(F1) = −0.92 on [F1] layers, and BVS(F2) = −1.13 and BVS(F3) = −1.07 on [M (=Ce0.95Ca0.05), F2, F3] layers, which were stacked alternately along the c-axis of the trigonal cell. The BVS(F2) value was relatively lower than the BVS(F1) and BVS(F3) ones, indicating that F2 is tightly bonded to M compared to that of F1 or F3. The findings suggested that F1−F1 and F1−F3 sublattices play a key role in the high mobility of the conducting F ions.