Abstract: The number of pixels scanned in star image can be large with conventional star tracking algorithm under large maneuvering of the vehicle. The feasibility of irrelevant star within threshold scan windows is increased. And the number of calculating angular separation between two stars is increased. This results in the decreasing of the update rate of star sensor. Therefore, the feasibility of error stars from star image is increased. Above all, an autonomous star tracking algorithm with high angle velocity was presented in this paper. Firstly, the next frame potential attitude was estimated according to previous attitudes. Secondly, the next frame ideal star centriodings of stars in FOV was calculated according to the potential attitude. Finally, all the real star centriodings would be obtained within the threshold scan windows of the ideal star centriodings. This algorithm can not only improve update rate of star sensor, but also avoid fault star pattern recognition. At last, the algorithm was tested by simulation and night sky experiment. The algorithm will be applied star sensor of satellite GNC.