Global Navigation Satellite System (GNSS) based navigation is already adopted in Low Earth Orbit (LEO), where the presence of strong GNSS signals and the good relative geometry between the receiver and the transmitters enable precise orbit determination. However, when the receiver is orbiting above the GNSS constellation’s altitude, designing an on-board, real-time, autonomous GNSS navigation device poses stringent requirements. Indeed, in such a challenging operational environment, the signal availability as well as the ranging error can be significantly influenced by the selection of the signals and their processing. In this paper, we define different tracking strategies which provide or not an ionosphere-free combination; for all altitudes or only for some altitudes; and for all the signals or for only those crossing the ionosphere. Then, we evaluate their effects on the signals availability; on the relative geometry between the receiver and the transmitters; and on the ranging error, in order to finally identify the best strategy. The analysis is performed for a GPS L1/L5 spaceborne receiver currently under development in our laboratory, specifically conceived for GNSS-based navigation from the Earth to the Moon.