Abstract: In allusion to the deficiencies of traditional inertial celestial integrated algorithm and selection uncertainty of the NAVSTAR, an algorithm based on SINS/CNS deeply integrated navigation with single star was proposed in this paper for the navigation system of long duration aero crafts. The error characteristics of inertial navigation and the star observation of two -gimbal were modeled exactly, and the advantages of both were analyzed and synthesized, the data of single star observation angle and inertial navigation was fused with high accuracy completely. In the height channel, barometric altimeter was introduced for altitude error damping. The design of the Kalman filter achieved optimal estimation of INS error. With analysis of the system observability, optimal NAVSTAR selection criteria was successfully brought out, effective solution to the problem of declining performance of the algorithm in the part of the observation angle was solved effectively. The simulation results of the algorithm show that the long positioning accuracy is better than traditional algorithm. Optimal NAVSTAR selection criteria effectively improve the robustness of the algorithm, which has a higher significance to theoretical study and engineering application value.