Low Earth orbit (LEO) satellites have unique advantages in navigation because of their high signal intensity and rapid geometric changes in a short period. In order to solve the problem of constellation performance degradation after a potential failure pertaining one or more medium Earth orbit (MEO) navigation satellites, this paper designs the LEO navigation constellation and considers the task requirements of different stages of constellation deployment. Firstly, the LEO navigation constellation is designed by a non-dominated sorting genetic algorithm II (NSGA-II). The average position dilution of precision (PDOP) is 1.676, which is an improvement compared to the average PDOP offered by the four traditional GNSS. Secondly, the staged deployment of constellation takes into account the degradation of constellation performance caused by the failure of MEO navigation satellites, and the Monte Carlo method is used to analyze the case of three simultaneous satellite failures. The results show that a single satellite failure within each orbital plane and adjacent satellites with close phase separation has a great impact on the performance of the MEO navigation constellation. On this basis, a staged deployment strategy was adopted in order to balance cost, risk, and performance. The three phases deploy 66, 156, and 288 satellites, respectively; as a make-up constellation under contingencies, a navigation enhancement constellation, and an independent navigation constellation, the deployment of the staged sub-constellations meets the mission requirements. The constellation design and staged deployment method proposed in this paper can provide reference for the future study of LEO navigation constellations.