For group-living animals traveling through heterogeneous landscapes, collective movement can be influenced by both habitat structure and social interactions. Yet research in collective behavior has largely neglected habitat influences on movement. Here we integrate simultaneous, high-resolution, tracking of wild baboons within a troop with a 3-dimensional reconstruction of their habitat to identify key drivers of baboon movement. A previously unexplored social influence – baboons’ preference for locations that other troop members have recently traversed – is the most important predictor of individual movement decisions. Habitat is shown to influence movement over multiple spatial scales, from long-range attraction and repulsion from the troop’s sleeping site, to relatively local influences including road-following and a short-range avoidance of dense vegetation. Scaling to the collective level reveals a clear association between habitat features and the emergent structure of the group, highlighting the importance of habitat heterogeneity in shaping group coordination.