This paper proposes an alternative environment mapping method for accurate robotic navigation based on 3D information. Typical techniques for 3D mapping using occupancy grid require intensive computational workloads in order to both build and store the map. This work introduces an Occupancy-Elevation Grid (OEG) mapping technique, which is a discrete mapping approach where each cell represents the occupancy probability, the height of the terrain and its variance. This representation allows a mobile robot to know with an accurate degree of certainty whether a place in the environment is occupied by an obstacle and the height of such obstacle. Thus, based on its hardware characteristics, it can make calculations to decide if it is possible to traverse that specific place. In general, the map representation introduced can be used in conjunction with any kind of distance sensor. In this work, we use laser range data and stereo system data with a probabilistic treatment. The resulting maps allow the execution of tasks as decision making for autonomous navigation, exploration, localization and path planning, considering the existence and the height of the obstacles. Experiments carried out with real data demonstrate that the proposed approach yields useful maps for autonomous navigation.