The roots of Uzes can be traced back to Oghuz Yabgu State (750-1055) located to the east of Caspian Sea. Oghuz State was the neighbour of the Khazar Khaganate in the west and north of the Caspian Sea. Oghuz-Khazar relations were not stable. Oghuz State was sometimes an ally and sometimes an enemy of the powerful Khazar Khaganate. In the 10th century a group of Oghuz people fought in the Khazar army. (Dukak, the father of Seljuk was one of them.) They fought mainly against Pechenegs, a rival Turkic people. After the Khazar Khaganate disintegrated, they had to move west because of Kypchaks raids from the east.

In 1054 they settled around Dnieper river. However five years later they were defeated by the Kievan Rus. They further moved west to Danube river where they were repelled by their old enemy the Pechenegs in 1065. After 1065 they paid hommage to Byzantine Empire and the Russian princes. Most of them converted to Christianity. They served as soldiers in the Byzantine Empire. During the battle of Manzikert between the Byzantines and the Seljuks in 1071 they served in the right flank of the Byzantine army. However according to some accounts they switched sides and contributed to the Seljuks victory.