This paper presents a new map specifically designed for robots operating in large environments and possibly in higher dimensions. We call this map the hierarchical atlas because it is a multilevel and multiresolution representation. For this paper, the hierarchical atlas has two levels: at the highest level there is a topological map that organizes the free space into submaps at the lower level. The lower-level submaps are simply a collection of features. The hierarchical atlas allows us to perform calculations and run estimation techniques, such as Kalman filtering, in local areas without having to correlate and associate data for the entire map. This provides a means to explore and map large environments in the presence of uncertainty with a process named hierarchical simultaneous localization and mapping. As well as organizing information of the free space, the map also induces well-defined sensor-based control laws and a provably complete policy to explore unknown regions. The resulting map is also useful for other tasks such as navigation, obstacle avoidance, and global localization. Experimental results are presented showing successful map building and subsequent use of the map in large-scale spaces.