The origin of the European bison (Bison bonasus, Linnaeus, 1758) has been widely discussed and investigated in recent years. The species had a wide historic geographic distribution throughout the European continent during the middle and late Holocene, ranging from France in the west to the Caucasus in the east. However, archaeological evidence is needed to resolve the southern extent of the European bison distribution. We discovered one bison skull fragment during archaeological excavations in 2008 in the area of Yenikapi Metro and Marmaray (Turkey). Radiocarbon dating indicated the skull was deposited during the Byzantine period (seventh to eighth century AD). Mitochondrial genome analyses provided clear evidence that the skull was from a European bison. This is the first unambiguous evidence of the presence of this species in southeastern Europe during Byzantine times, which validates the historical written records of a potentially wider range of the European bison in historical times.