The construction of a guide star catalog is crucial for a star sensor to achieve accurate star map recognition and attitude determination. At present, the methods of a guide star catalog for a large field of view (FOV) star sensor have been relatively mature. However, for a small-FOV star sensor, there are still certain problems, such as a large storage capacity of a guide star catalog, uneven distribution of stars, and easy occurrence of voids. To address these problems, we propose a construction method of a small-FOV star sensor guide star catalog based on the combination of the improved spherical spiral method (ISSM) and extreme learning machine (ELM) named the ISSM-ELM. First, a spiral reference point is used as an optical axis pointing of the star sensor, and the guide stars are preliminarily screened based on the star-diagonal distance between the star and the reference point, and the star-density and magnitude characteristics of the guide star. Then the ELM is used to supplement the guide star empty sky area to construct an integrity guide star catalog. The experimental results demonstrate that the proposed method can reduce the storage capacity of the guide star catalog, and improve its uniformity, integrity, and average brightness.