There is widespread concern about impacts of land-use change on connectivity among animal and plant populations, but those impacts are difficult to quantify. Moreover, lack of knowledge regarding ecosystems before fragmentation may obscure appropriate conservation targets. We use occurrence and population genetic data to contrast connectivity for a long-lived mega-herbivore over historical and contemporary time frames. We test whether (i) historical gene flow is predicted by persistent landscape features rather than human settlement, (ii) contemporary connectivity is most affected by human settlement and (iii) recent gene flow estimates show the effects of both factors. We used 16 microsatellite loci to estimate historical and recent gene flow among African elephant (Loxodonta africana) populations in seven protected areas in Tanzania, East Africa. We used historical gene flow (FST and G'ST) to test and optimize models of historical landscape resistance to movement. We inferred contemporary landscape resistance from elephant resource selection, assessed via walking surveys across ~15 400 km2 of protected and unprotected lands. We used assignment-based recent gene flow estimates to optimize and test the contemporary resistance model, and to test a combined historical and contemporary model. We detected striking changes in connectivity. Historical connectivity among elephant populations was strongly influenced by slope but not human settlement, whereas contemporary connectivity was influenced most by human settlement. Recent gene flow was strongly influenced by slope but was also correlated with contemporary resistance. Inferences across multiple timescales can better inform conservation efforts on large and complex landscapes, while mitigating the fundamental problem of shifting baselines in conservation.