It is known that Strapdown Inertial Navigation System (SINS), Global Navigation Satellite System (GNSS) and Celestial Navigation System (CNS) can complement each other’s advantages. The SINS/CNS integrated system, which has the characteristics of strong autonomy, high accuracy and good anti-jamming, is widely used in military and civilian applications. Similar to SINS/GNSS integrated system, the SINS/CNS integrated system can also be divided into three kinds according to the difference of integrating depth, i.e., loosely coupled pattern, tightly coupled pattern and deeply coupled pattern. In this paper, the principle and characteristics of each pattern of SINS/CNS system are analyzed. Based on the comparison of these patterns, a novel deeply coupled SINS/CNS integrated navigation scheme is proposed. The innovation of this scheme is that a new star pattern matching method aided by SINS information is put forward. Thus the complementary features of these two subsystems are reflected.