To solve the signal synchronization problem caused by the wide range of time delay and frequency shift of the satellite-based automatic identification system (AIS), a new frame header detection algorithm based on differential phase waveform matching is proposed. The theoretical analysis of the phase characteristics of the signal of the training sequence and the start flag in the AIS frame structure, and the use of a specific matching algorithm to detect the frame header. The simulation results show that the algorithm has good properties in frequency shift resistance, and has a high detection rate, low frame error rate, and false alarm rate under low SNR. Compared with other algorithms, the computational complexity proposed in this article is very low, and the hardware resource consumption of FPGA is low.