The second and third phases of the Chinese Lunar Exploration Program (CLEP) are planning to achieve Moon landing, surface exploration and automated sample return. In these missions, the inertial navigation system (INS) and celestial navigation system (CNS) are two indispensable autonomous navigation systems which can compensate for limitations in the ground based navigation system. The accurate initialization of the INS and the precise calibration of the CNS are needed in order to achieve high navigation accuracy. Neither the INS nor the CNS can solve the above problems using the ground controllers or by themselves on the lunar surface. However, since they are complementary to each other, these problems can be solved by combining them together. A new celestial assisted INS initialization method is presented, in which the initial position and attitude of the explorer as well as the inertial sensors’ biases are estimated by aiding the INS with celestial measurements. Furthermore, the systematic error of the CNS is also corrected by the help of INS measurements. Simulations show that the maximum error in position is 300 m and in attitude 40″, which demonstrates this method is a promising and attractive scheme for explorers on the lunar surface.