Whatever the truth of this, the Pechenegs emerge in the historical records only in the 8th and 9th centuries, inhabiting the region between the lower Volga, the Don, and the Ural Mountains. By the 9th and 10th centuries AD they controlled much of the steppes of southwestern Eurasia and the Crimean Peninsula. Although an important factor in the region at the time, like most nomadic tribes their concept of statecraft failed to go beyond random attacks on neighbours and spells as mercenaries for other powers.
According to Constantine Porphyrogenitus, writing in c. 950, Patzinakia, the Pecheneg realm, stretched west as far as the Siret River (or even the Eastern Carpathian Mountains), and was four days distant from "Tourkias" (i.e. Hungary).
(Constantine Porphyrogenitus, De Administrando Imperio, c. 950, translation by R.J.H. Jenkins)
In the Armenian chronicles of Matthew of Edessa Pechenegs are mentioned a couple of times. The first mention is in chapter 75, where it says that in the year 499 (according to the old Armenian calendar — years 1050–51 according to the Gregorian calendar) the Badzinag nation caused great destruction in many provinces of Rome, i.e. the Byzantine territories. The second is in chapter 103, which is about the Battle of Manzikert. In that chapter it is told that the allies of Rome, Padzunak and Uz (some branches of the Oghuz Turks) tribes which changed their sides at the peak of the battle and began fighting against the Byzantine forces, (side by side with the Seljuk Turks). In the 132nd chapter a war between Rome and the Padzinags is described and after the defeat of the Roman (Byzantine) Army, an unsuccessful siege of Constantinople by the Padzinags is mentioned. In that chapter, the Patzinags are described as an "all archer army". In chapter 299, the Armenian prince, Vasil, who was in the Roman Army, sent a platoon of Padzinags (they had settled in the city of Misis, around modern Adana, which is far away from the lands where Pechenegs were then mainly living) to the aid of the Christians.
In the 9th century, the Byzantines became allied with the Pechenegs, using them to fend off other, more dangerous tribes such as the Rus and the Magyars. This was an old Roman ploy (divide and rule) continued by their Byzantine successors — playing off one enemy tribe against another.
The Uzes, another Turkic steppe people, eventually expelled the Pechenegs from their homeland; in the process, they also seized most of their livestock and other goods. An alliance of the Oghuz, Kimeks and Karluks was also pressing the Pechenegs, but another group, the Samanids, defeated that alliance. Driven further west by the Khazars and Cumans by 889, the Pechenegs in turn drove the Magyars west of the Dnieper River by 892.
In 894, the Bulgarians went to war against Byzantium. Early in 895, Emperor Leo VI the Wise invoked the help of the Magyars, who sent an army under a commander named Levente into Bulgaria. Levente conducted a brilliant campaign and invaded deep into Bulgaria, while the Byzantine army entered Bulgaria from the south. Caught in a vice of Magyar and Byzantine forces, Tsar Simeon I realised he could not fight a war on two fronts, and quickly concluded an armistice with the Byzantine Empire.
Tsar Simeon also employed the Pechenegs to help fend off the Magyars. The Pechenegs were so successful that they drove out the Magyars remaining in Etelköz and the Pontic steppes, forcing them westward up the lower Danube, Transdanubia and towards the Pannonian plain, where they later founded a Hungarian state.
From the 9th century AD, the Pechenegs started an uneasy relationship with Kievan Rus. For more than two centuries they launched random raids into the lands of Rus, which sometimes escalated into full-scale wars (like the 920 war on the Pechenegs by Igor of Kiev reported in the Primary Chronicle), but there were also temporary military alliances (e.g. 943 Byzantine campaign by Igor). In 968, the Pechenegs attacked and then besieged the city of Kiev.
Part of them joined the Prince of Kiev Sviatoslav I in his Byzantine campaign of 970–971, though eventually the Pechenegs ambushed and killed the Kievan prince in 972, and according to the Primary Chronicle, the Pecheneg Khan Kurya made a chalice from his skull—a traditional steppe nomad custom. The fortunes of the Rus-versus-Pecheneg confrontation swung during the reign of Vladimir I of Kiev (990–995), who founded the town of Pereyaslav upon the site of his victory over the Pechenegs, but were followed by the defeat of the Pechenegs during the reign of Yaroslav I the Wise (1037). Shortly afterwards, the decimated Pechenegs were replaced in the Pontic steppe by another nomadic Turkic people—the Cumans or Polovtsy.
After centuries of fighting involving all their neighbours—the Byzantine Empire, Bulgaria, Kievan Rus, Khazaria and the Magyars—the Pechenegs were annihilated as an independent force at the Battle of Levounion by a combined Byzantine and Cuman army under Byzantine Emperor Alexios I Komnenos in 1091. Attacked again in 1094 by the Cumans, many Pechenegs were slain or absorbed. They were again defeated by the Byzantines at the Battle of Beroia in 1122, on the territory of modern day Bulgaria. For some time, significant communities of Pechenegs still remained in Hungary, but finally the Pechenegs ceased to be a distinct people and were assimilated into their neighbours—Bulgarians, Magyars and Gagauz. In the 15th century Hungary some people adopted the surname Besenyö, which is Hungarian for Pecheneg. They were most numerous in county Tolna. Abu Hamid al Garnathi in the late 12th century referred to Hungarian Pechenegs who were probably Muslims living disguised as Christians. Others survived within the ranks of the pastoral nomadic tribes of the Balkan Highlands as Yörüks, eventually adopting Islam.