We present a 3D mesh surface navigation system for mobile robots. This system uses a 3D point cloud to reconstruct a triangle mesh of the environment in real time that is enriched with a graph structure to represent local connectivity. This Navigation Mesh is then analyzed for roughness and trafficability and used for online path planning. The presented approach is evaluated with a VolksBot XT platform in a real life outdoor environment.