This paper presents two techniques to detect and classify navigable terrain in complex three‐dimensional (3D) environments. The first method is a low level on‐line mechanism aimed at detecting obstacles and holes at a fast frame rate using a time‐of‐flight camera as the main sensor. The second technique is a high‐level offline classification mechanism that learns traversable regions from larger 3D point clouds acquired with a laser range scanner. We approach the problem using Gaussian processes as a regression tool, in which the terrain parameters are learned, and also for classification, using samples from traversed areas to build the traversable terrain class. The two methods are compared against unsupervised classification, and sample trajectories are generated in the classified areas using a nonholonomic path planner. We show results of both the low‐level and the high‐level terrain classification approaches in simulations and in real‐time navigation experiments using a Segway RMP400 robot.