Of all current methods for measuring spacecraft attitude, the use of star sensors produces the most accurate measurements. Conventional star sensors repeat these processes with Lost-In-Space case. To advance the methods available to solve these problems, this paper presents an autonomous predictive centroiding algorithm for the star sensor. The star sensor works in the star predictive centroiding case while few recognized stars within the FOV (Field of View). The ideal locations of unrecognized stars and recognized stars in star image are predicted at first. Then the corresponding real locations of recognized stars and unrecognized stars are obtained in the threshold scan window of predictive centroiding. It enables only several hundred pixels to be scanned. The speed and the accuracy of this algorithm are successfully demonstrated in comparison with the ordinary centroiding algorithms which don't use the previous image data. Finally the autonomous predictive centroiding algorithm was successfully demonstrated with real sky experiment in 2008 and on-orbit in 2010.