Autonomous navigation is an important function for a Mars rover to fulfill missions successfully. It is a critical technique to overcome the limitations of ground tracking and control traditionally used. This paper proposes an innovative method based on SINS (Strapdown Inertial Navigation System) with the aid of star sensors to accurately determine the rovers position and attitude. This method consists of two parts: the initial alignment and navigation. The alignment consists of a coarse position and attitude initial alignment approach and fine initial alignment approach. The coarse one is used to determine approximate position and attitude for the rover. This is followed by fine alignment to tune the approximate solution to accurate one. Upon the completion of initial alignment, the system can be used to provide real-time navigation solutions for the rover. An autonomous navigation algorithm is proposed to estimate and compensate the accumulated errors of SINS in real time. High accuracy attitude information from star sensor is used to correct errors in SINS. Simulation results demonstrate that the proposed methods can achieve a high precision autonomous navigation for Mars rovers. © 2014 IAA.