Нашествие гуннов имело крайне тяжелые последствия для Северного Кавказа. Походы завоевателей сопровождались грабежом и разорением, истреблением местного населения. Многие северокавказские племена оказались вовлеченными в войны гуннов с Ираном и Византией, а отдельные районы превратились в арену кровопролитных сражений. Нашествие гуннов заметно изменило политическую и этническую ситуацию на Северном Кавказе. Было уничтожено Боспорское царство, разрушены многие города Северного и Восточного Причерноморья. Резко ухудшилось положение адыгейских племен. В IV–V вв. гунны были силой, наводившей страх на весь цивилизованный мир, прежде всего на Римскую империю. Однако военно-политическое объединение, созданное гуннами, было нестабильным. Гуннская держава, упрочивавшаяся под властью бича народов Аттиллы, после его смерти в 453 году стала распадаться. Но обстановка в южнорусских и северокавказских степях продолжала оставаться очень сложной. В середине VI в. в степях Восточной Европы сложился союз кочевых племен во главе с аварами. В это же время в Приазовье кочевали болгарские племена, у которых в 635 г. также образовался сильный союз племен во главе с Кубратом. В VII в. под контролем этого союза находились земли Прикубанья, нижнего течения Дона, Северного и Восточного Приазовья. Под покровительством болгар возродились к жизни многие города, а древняя Фанагория, вероятно, считалась столицей Болгарского государства — так называемой Великой Болгарии. Однако это государство просуществовало недолго. После смерти хана Кубрата в 668 г. Великая Болгария распалась на ряд орд, возглавляемых его сыновьями, между которыми началась междоусобная борьба. Мощный удар болгарам нанесли их восточные соседи — хазары. В результате часть болгар ушла на Дунай и образовала новое государство — Дунайскую Болгарию. Другая часть осталась в Приазовье и Прикубанье. Третья же часть болгар переселилась на север к Дону, а оттуда — на Волгу, положив тем самым начало Волжской Булгарии.
Прикубанские болгары были подчинены хазарам и вошли в состав Хазарского каганата, представлявшего собой обширную федерацию различных племен, власть которого распространялась к концу VII в. не только на степи между Азовским и Каспийским морями, но и на Северное Причерноморье и часть степного Крыма. В IX в. администрация юго-западной части Хазарии переселилась в бывшую античную Гермонассу. Город получил хазарское название Тумен-Тархан, т. е. место ставки военачальника. Это давало возможность хазарам постоянно контролировать Керченский пролив и весь Таманский полуостров, заселенный в основном адыгейскими и болгарскими племенами. Адыгейское название этого города Тамтаракай, а в русских летописях — Тмутаракань. Еще в VII в. на территории Хазарии начинает распространяться христианство. Но в начале IX в. в каганате было официально принято иудейство. Однако новая религия не только не объединила, а, наоборот, разъединила и без того непрочное государственное образование, каким был хазарский каганат, началась междоусобная борьба. В этих условиях на территорию каганата вторглись кочевнические орды венгров и печенегов. Последние вытеснили хазар из Крыма, под их ударами погибли Фанагория и приморские поселения на Боспоре.
Сокрушительный удар хазарам нанес в 965 г. великий князь Киевский Святослав Игоревич. Как говорит «Повесть временных лет», Святослав разгромил войско хазарского кагана, в составе которого были аланы и касоги, захватил главные города Хазарии Итиль (недалеко от устья Волги) и Семендер (в Дагестане). После этого стало реальностью продвижение руссов на Северный Кавказ. Вскоре хазарский город Таматарха становится русской Тмутараканью (ныне ст-ца Тамань) и центром одноименного княжества. Оно занимало Таманский полуостров, восточную часть Керченского полуострова и, возможно, низовья Кубани.
Положение руссов упрочилось после того, как Киевский князь Владимир Святославович взял в 989 г. Херсонес (Корсунь) и посадил на княжение в Тмутаракани своего воинственного сына Мстислава. Стараясь укрепить и расширить свои владения, Тмутараканский князь Мстислав Владимирович в 1022 г. (как сообщает Лаврентьевская летопись) совершил поход на касогов (адыгов). Касожское войско под предводительством князя Редеди выступило ему навстречу. Касожский князь по обычаю того времени вызвал Мстислава на поединок «не оружием, но борьбою». «Если одолеешь ты, то возьмешь именье мое и жену мою, и детей моих, и землю мою, — сказал Редедя, — а еще аз одолею, то возьму твое все». Далее летопись сообщает, что в критический для Мстислава момент единоборства последний против правил «вынзе ножь и убил Редедю. И взя все именье его, жену его, и детей его, и дань возложен на касоты».
