We describe a system which follows “trails” for autonomous outdoor robot navigation. Through a combination of visual cues provided by stereo omnidirectional color cameras and ladar-based structural information, the algorithm is able to detect and track rough paths despite widely varying tread material, border vegetation, and illumination conditions. The approaching trail region is simply modeled as a circular arc of constant width. Using an adaptive measure of color and brightness contrast between a hypothetical region and flanking areas, the tracker performs a robust randomized search for the most likely trail region and robot pose relative to it with no a priori appearance model. Stereo visual odometry improves tracker dynamics on uneven terrain and permits local obstacle map maintenance. A motion planner is also described which takes the trail shape estimate and local map to plan smooth trajectories around in-trail and near-trail hazards. Our system's performance is analyzed on several long sequences with diverse appearance and structural characteristics using ground-truth segmentations.