Fluorite-structure solid solutions with ultrahigh fluoride ion mobility are widely recognized as promising solid electrolytes for applications in solid-state electrochemical devices like fluoride ion batteries (FIBs). Herein, solid solutions in the PbF2-CaF2-KF system were prepared by mechanochemical synthesis. The structure and morphology of the synthesized solid solutions are studied by X-ray diffraction (XRD), scanning electron microscopy (SEM), transmission electron microscopy (TEM), and high-resolution transmission electron microscopy (HRTEM). The fluoride ion conductivity of the samples is investigated by the electrochemical impedance spectroscopy (EIS). The results show that the fluorite-structure solid electrolyte β-Pb0.75Ca0.2K0.05F1.95 with high ionic conductivity (1.46 × 10−3 S/cm at 20 °C) can be obtained combined with brief low-temperature heat treatment.