Navigating autonomously is one of the most important problems facing outdoor mobile robots. This task is extremely difficult if no prior information is available and is trivial if perfect prior information is available and the position of the robot is precisely known. Perfect prior maps are rare, but good-quality, high-resolution prior maps are increasingly available. Although the position of the robot is usually known through the use of the Global Position System (GPS), there are many scenarios in which GPS is not available, or its reliability is compromised by different types of interference such as mountains, buildings, foliage or jamming. If GPS is not available, the position estimate of the robot depends on dead-reckoning alone, which drifts with time and can accrue very large errors. Most existing approaches to path planning and navigation for outdoor environments are unable to use prior maps if the position of the robot is not precisely known. Often these approaches end up performing the much harder task of navigating without prior information. This thesis addresses the problem of planning paths with uncertainty in position for large outdoor environments. The objective is to be able to reliably navigate autonomously in an outdoor environment without GPS through the use of high resolution prior maps and a good dead-reckoning system. Different approaches to the problem are presented, depending on the types of landmarks available, the accuracy of the map and the quality of the perception system. These approaches are validated in simulations and field experiments on an e-gator robotic platform.