Abstract: An autonomous navigation method based on the observations of the relativistic perturbations for deep space probes is presented in this paper. The relativistic perturbations including the stellar aberration and the starlight gravitational deflection are new type of celestial navigation measurement, which can provide the kinematic state information of the deep space probes in the inertial frame. In the relativistic navigation system, the position and velocity vectors of the deep space probes, and the measurement bias of the optical sensor can be estimated through measuring the inter-star angle perturbed by the stellar aberration and the gravitational deflection of light with an optical sensor for LOS (line-of-sight) direction with extremely high accuracy. In this paper, the state equation and measurement equation for the design of the navigation filter and the navigation performance evaluation are established. The feasibility of the relativistic navigation method for deep space probes is investigated via the calculation of the Cramer-Rao Lower Bound (CRLB). In addition, the self-learning strategy of the navigation filter is designed to enhance the relativistic navigation performance. It is illustrated through the numerical simulation that, for a Mars-circling probe, the position error of the relativistic navigation method is on the order of 100 m with the inter-star angle measurement accuracy of 1 mas.