Autonomous orbit determination of a navigation constellation is the process by which the orbit parameters of navigation satellites are autonomously calibrated onboard the satellites without the need for external aids. It commonly uses a satellite onboard data processing unit and a filtering method to process the measurements of inter-satellite ranges. The onboard data processing unit is the main module of autonomous navigation systems. In this paper, the two main factors that affect the accuracy of autonomous orbit determination for a navigation constellation are discussed first, and then a distributed onboard algorithm for autonomous orbit determination of navigation satellites is proposed. This method is based on a long-term ephemeris prediction and is suitable for the satellite hardware capability. The main feature of this method is that both the distributed computing method and an onboard analytical state transition matrix are used to process inter-satellite range measurements. One of the main advantages of this approach is high-speed computing since the amount of calculations needed is significantly less than that of the centralised computing method and those distributed methods that need to use an onboard numerical integrator. Another advantage of this approach is that the use of the onboard analytical state transition matrix algorithm can save a great amount of resources for both ground-to-satellite data transmissions and data storage units in satellites’ hardware. This could result in substantial cost reduction for space missions. Finally, a simulation method used for testing the proposed algorithm is presented. Results of tests over a period of 90 days show that the user range error of autonomous orbit determination derived from the proposed method is less than three metres.