Abstract: The success of NASA's Mars Exploration Rovers has demonstrated the important benefits that mobility adds to planetary exploration. Very soon, mission requirements will impose that planetary exploration rovers drive over-the-horizon in a single command cycle. This will require an evolution of the methods and technologies currently used. This paper presents experimental validation of our over-the-horizon autonomous planetary navigation. We present our approach to 3D terrain reconstruction from large sparse range data sets, localization and autonomous navigation in a Mars-like terrain. Our approach is based on on-line acquisition of range scans, map construction from these scans, path planning and navigation using the map. An Autonomy Engine supervises the whole process ensuring the safe navigation of the planetary rover. The outdoor experimental results demonstrate the effectiveness of the reconstructed terrain model for rover localization, path planning and motion execution scenario as well as the autonomy capability of our approach.