In this paper, a new method for novel X-ray pulsar navigation was proposed to overcome the Doppler effects from the motion of the deep space explorer. An analysis was undertaken of the dynamic orbit model of the interplanetary trajectory cruise phase. During a pulsar signals observation period, the deep space explorer can be considered as a constant acceleration motion. A Doppler compensation method was proposed based on this analysis. The method demonstrated great advantages in terms of low computational cost. However, there is an evident bias due to the Doppler compensation in the pulse time-of-arrival (TOA). Moreover, the pulse TOA bias and the velocity estimation error of the deep space explorer are correlated, resulting in a decline in Kalman filter performance. To deal with this problem, we constructed the TOA measurement bias model with respect to the state estimation error, and developed an extended Kalman filter (EKF) with correlated measurement bias and state estimation error. Results from the simulation suggested that the proposed navigation method is feasible, accurate and effective. The proposed navigation method based on EKF with correlated measurement bias and state estimation error proves more accurate than a traditional EKF-based method.