Significance Elephantids were once among the most widespread megafaunal families. However, only three species of this family exist today. To reconstruct their evolutionary history, we generated 14 genomes from living and extinct elephantids and from the American mastodon. While previous studies examined only simple bifurcating relationships, we found that gene flow between elephantid species was common in the past. Straight-tusked elephants descend from a mixture of three ancestral populations related to the ancestor of African elephants, woolly mammoths, and present-day forest elephants. We detected interbreeding between North American woolly and Columbian mammoths but found no evidence of recent gene flow between forest and savanna elephants, demonstrating that both gene flow and isolation have been central in the evolution of elephantids.