Печенезите се јавуваат во историски извори од 8 и 9 век. Тогаш се населиле во областите помеѓу долниот дел наВолга,Дон иУрал. Веќе од 9 и 10 век контролирале голем дел од југозападна Евроазија иКрим. Во тоа време, тие биле значаен фактор во областа, но како и повеќето номадски народи немале концепт на држава, а нивната организација се сведувала на случајни напади врз соседите. Покрај тоа, тие биле платеници за други сили. Според Константин Порфирогенит, Печенезите владееле со местото западно од реката Серет.
Во 9 век,Византија станала сојузник на Печенезите, користејќи ги за да се заштити од други поопасни племиња, како на пример одУнгарците или Варјазите. Византија го направила ова според римската политика, „раздели па владеј“, ги упатувала непријателите еден против друг.
Туркиското племе Узи ги протерало Печенезите од нивната татковина. Печенезите до889 година биле туркани кон запад одХазарите иКуманите, па Печенезите ги потисналеУнгарците западно од Днепар до892 година.
