Terrestrial wildlife migrations, once common, are now rare because of ecosystem fragmentation and uncontrolled hunting. Botswana historically contained migratory populations of many species but habitat fragmentation, especially by fences, has decreased the number and size of many of these populations. During a study investigating herbivore movement patterns in north-west Botswana we recorded a long-distance zebra Equus burchelli antiquorum migration between the Okavango Delta and Makgadikgadi grasslands, a round-trip distance of 588 km; 55% of 11 animals collared in the south-eastern peripheral delta made this journey. This was unexpected as, between 1968 and 2004, the migration could not have followed its present course because of the bisection of the route by a veterinary cordon fence. As little evidence exists to suggest that large-scale movements by medium-sized herbivores can be restored, it is of significant interest that this migration was established to the present highly directed route within 4 years of the fence being removed. The success of wildlife corridors, currently being advocated as the best way to re-establish ecosystem connectivity, relies on animals utilizing novel areas by moving between the connected areas. Our findings suggest that medium-sized herbivores may be able to re-establish migrations relatively quickly once physical barriers have been removed and that the success of future system linkages could be increased by utilizing past migratory routes.