With the improving detection sensitivity of star sensors, the number of stars in star catalogs has increased dramatically, reducing the speed and rate of star identification. To improve the identification speed and rate, a fast star identification algorithm based on multi-feature matching and built upon the foundation of the triangle algorithm was proposed. First, the preprocessed star catalog was partitioned using the inserted icosahedron of the celestial sphere. Then, the navigation feature library was constructed with the sides and the product of the radii of circumcircles and incircles as feature values. In addition, the navigation feature library was stored in blocks according to the hash function of the latter feature value. In the process of star identification, the product of the radii of the circumcircle and incircle in the observation triangle was used to rapidly locate the block of the navigation feature library, and then the observation triangle was identified in the block by using multi-feature matching. Finally, the sub-regions of the celestial sphere in the field of view were obtained, and then other navigation stars were identified in the sub-regions. The experimental results indicate that the identification performance of the proposed algorithm is related to the number of blocks. Based on a reasonable number of blocks, the proposed algorithm has advantages in identification speed and rate as well as in its robustness to star magnitude noise and false stars, compared with common triangle algorithms. The average identification time and rate of the proposed algorithm are 17.161 ms and 98.58%, respectively, which can meet the star sensor requirements for high identification speed and rate.