The phylogenetic position of the giant panda, Ailuropoda melanoleuca (Carnivora: Ursidae: Ailuropodinae), has been one of the most hotly debated topics by mammalian biologists and paleontologists during the last century. Based on molecular data, it is currently recognized as a true ursid, sister-taxon of the remaining extant bears, from which it would have diverged by the Early Miocene. However, from a paleobiogeographic and chronological perspective, the origin of the giant panda lineage has remained elusive due to the scarcity of the available Miocene fossil record. Until recently, the genus Ailurarctos from the Late Miocene of China (ca. 8-7 mya) was recognized as the oldest undoubted member of the Ailuropodinae, suggesting that the panda lineage might have originated from an Ursavus ancestor. The role of the purported ailuropodine Agriarctos, from the Miocene of Europe, in the origins of this clade has been generally dismissed due to the paucity of the available material. Here, we describe a new ailuropodine genus, Kretzoiarctos gen. nov., based on remains from two Middle Miocene (ca. 12-11 Ma) Spanish localities. A cladistic analysis of fossil and extant members of the Ursoidea confirms the inclusion of the new genus into the Ailuropodinae. Moreover, Kretzoiarctos precedes in time the previously-known, Late Miocene members of the giant panda clade from Eurasia (Agriarctos and Ailurarctos). The former can be therefore considered the oldest recorded member of the giant panda lineage, which has significant implications for understanding the origins of this clade from a paleobiogeographic viewpoint.