The study of spatial cognition has provided considerable insight into how animals (including humans) navigate on the horizontal plane. However, the real world is three-dimensional, having a complex topography including both horizontal and vertical features, which presents additional challenges for representation and navigation. The present article reviews the emerging behavioral and neurobiological literature on spatial cognition in non-horizontal environments. We suggest that three-dimensional spaces are represented in a quasi-planar fashion, with space in the plane of locomotion being computed separately and represented differently from space in the orthogonal axis - a representational structure we have termed "bicoded." We argue that the mammalian spatial representation in surface-travelling animals comprises a mosaic of these locally planar fragments, rather than a fully integrated volumetric map. More generally, this may be true even for species that can move freely in all three dimensions, such as birds and fish. We outline the evidence supporting this view, together with the adaptive advantages of such a scheme.