This paper presents the approach, algorithms and processes we developed to perform autonomous navigation in a natural environment. After a description of the global approach, we discuss the characteristics of natural environment representations. Then the perception functions for terrain mapping and robot localization, as well as motion planning are described. Navigation strategies for selecting perception tasks and subgoals for motion planning are proposed. The current state of integration in the experimental test bed EDEN is finally presented. Results from this experiment illustrate the approach troughout the paper.