According to the high precision demand of estimating frequency of arrival (FOA) and time of arrival (TOA) in Galileo search and rescue (SAR) system, and considering the uncertainty of message bit width in actual received COSPAS-SARSAT beacons, a new FOA and TOA estimation algorithm which combines the Multiple Dimensions Joint Maximum Likelihood Estimation (MJMLE) algorithm and Barycenter calculation algorithm is proposed. The principle of the algorithm is derived and the concrete realization of the algorithm is given. Both Monte Carlo simulation and experimental results show that when CNR equals to the threshold of 34.8dBHz, root-mean-square errors (rmse) of FOA and TOA estimation in this algorithm are respectively within 0.03Hz and 9.5us, which are less than the system requirements of 0.05Hz and 11us. This algorithm has been applied to the Galileo Medium-altitude Earth Orbit Local User Terminal (MEOLUT station).