This dissertation introduces a relativistic autonomous observation model that takes special relativistic mechanics as a baseline and is more general than Einstein’s observation model. Next, it presents two autonomous navigation methods that build on the relativistic autonomous observation model. These methods utilize an onboard star catalog and astrometry and spectrometry sensors and estimate astrometric and spectrometric quantities in addition to spacecraft position and velocity. A case study investigates the performance of both navigation methods in the context of technological details of a near-term mission, including certain sources of noise and disturbance in the interstellar medium. Results of the case study suggest that these methods are suitable for any spacecraft for which relativistic effects are detectable onboard. Moreover, the methods’ success in estimating astrometric and spectrometric quantities may enable means of updating the star-catalog during the mission and may improve the accuracy of our current star catalogs. Finally, the dissertation presents a technology-push mission concept for an interstellar dark matter explorer mission that the two navigation methods enable. This mission concept employs well-understood and space-demonstrated technology of several heritage spacecraft. It proposes a new idea to detect deviations in the dark matter distribution within the solar system and looks promising even in this early development stage. Overall, this dissertation represents a foundational step in the development of interstellar navigation technology and interstellar dark matter exploration missions.