The straight-tusked elephants Palaeoloxodon spp. were widespread across Eurasia during the Pleistocene. Phylogenetic reconstructions using morphological traits have grouped them with Asian elephants (Elephas maximus), and many paleontologists place Palaeoloxodon within Elephas. Here, we report the recovery of full mitochondrial genomes from four and partial nuclear genomes from two P. antiquus fossils. These fossils were collected at two sites in Germany, Neumark-Nord and Weimar-Ehringsdorf, and likely date to interglacial periods ~120 and ~244 thousand years ago, respectively. Unexpectedly, nuclear and mitochondrial DNA analyses suggest that P. antiquus was a close relative of extant African forest elephants (Loxodonta cyclotis). Species previously referred to Palaeoloxodon are thus most parsimoniously explained as having diverged from the lineage of Loxodonta, indicating that Loxodonta has not been constrained to Africa. Our results demonstrate that the current picture of elephant evolution is in need of substantial revision.