The 2013–2016 epidemic of Ebola virus disease in West Africa was of unprecedented magnitude, duration and impact. Extensive collaborative sequencing projects have produced a large collection of over 1600 Ebola virus genomes, representing over 5% of known cases, unmatched for any single human epidemic. In a comprehensive analysis of this entire dataset, we reconstruct in detail the history of migration, proliferation and decline of Ebola virus throughout the region. We test the association of geography, climate, administrative boundaries, demography and culture with viral movement among 56 administrative regions. Our results show that during the outbreak viral lineages moved according to a classic 'gravity' model, with more intense migration between larger and more proximate population centers. Despite a strong attenuation of international dispersal after border closures, localized cross-border transmission beforehand had already set the seeds for an international epidemic, rendering these measures relatively ineffective in curbing the epidemic. We use this empirical evidence to address why the epidemic did not spread into neighboring countries, showing that although these regions were susceptible to developing significant outbreaks, they were also at lower risk of viral introductions. Finally, viral genome sequence data uniquely reveals this large epidemic to be a heterogeneous and spatially dissociated collection of transmission clusters of varying size, duration and connectivity. These insights will help inform approaches to intervention in such epidemics in the future.