Deep space exploration is in the agenda of the major space agencies worldwide and at least the European Space Agency (SMART & Aurora Programs) and the American NASA (New Millennium Program) have set up programs to allow the development and the demonstration of technologies that can reduce the risks and the costs of the deep space missions.Navigation is the Achilles’ heel of deep space. Being performed on ground, it imposes considerable constraints on the system and the operations, it is very expensive to execute, especially when the mission lasts several years and, above all, it is not failure tolerant. Nevertheless, up to now, ground navigation has been the only possible solution.The technological breakthrough of advanced star trackers, like the micro-advanced stellar compass (μASC) might change this situation. Indeed, exploiting the capabilities of this instrument, the authors have devised a method to determine the orbit of a spacecraft autonomously, on-board and without any a priori knowledge of any kind. The solution is robust, elegant and fast.This paper presents the preliminary performances obtained during the ground tests. The results are very positive and encouraging.