В 576 г. тюркский каган Турксанф направил свои орды на завоевание Боспора, объявив тем самым войну самой Византийском империи. Города Таманского полуострова вновь подверглись нападению, и некоторые из них закончили свое существование. Однако кочевники, по всей видимости, понимали, что городские кварталы трудно превратить в пастбища для овец. Значительно выгоднее было обложить их данью и держать в постоянном страхе.
Известно, что вождь болгар Кубрат сумел освободиться из-под власти кагана и основал в Приазовье самостоятельное государство под названием «Великая Болгария». В его состав вошли вытесненные тюрками из Северного Кавказа ираноязычные аланы и остатки жителей Боспорского царства. Правда, столицей нового государства стала не Гермонасса, расположенная почти посередине нынешнего Керченского пролива, а разрушенная Фанагория, лежавшая существенно ближе к Азову. Наследник Кубрата – его сын Батбай – остался на Таманском полуострове и признал власть хазар. Все эти события произошли в середине VII в. С этого времени Таманский полуостров стал частью первого в Восточной Европе раннефеодального государства – Хазарского каганата.
Таманские города стали принимать участие в политической жизни Хазарии и Византии. Так, в конце VII в. в Фанагории жил свергнутый с престола император Юстиниан II. Хазарский каган выдал за него замуж свою сестру, названную при крещении Феодорой. При Юстиниане находился личный представитель кагана Папаций, который совместно с византийцами организовал заговор против опального императора. Феодора предупредила мужа о грозящей опасности, и Юстиниан уничтожил заговорщиков, а позднее, как известно, вернул себе византийский престол.
Крупнейшим городом Хазарского каганата на Таманском полуострове стала Таматарха – бывшая греческая Гермонасса. В VIII в. здесь была основана самостоятельная Таматархская епархия – несомненный признак возросшего значения города для региона.
По мнению выдающегося русского историка Г.В. Вернадского, само название города, скорее всего, происходит от алтайских слов «тма» (ср. персидское «туман») – военный отряд в десять тысяч человек – и «тархан» (вождь). «Предположительно, во время тюркского вторжения на Северный Кавказ в VI в. командующий тюркским отрядом «тма-тархан» устроил свой штаб в дельте Кубани, отсюда и название города», – пишет Г.В. Вернадский. Греки эллинизировали название, изменив его на Tnmatarca, или Таматарха. Поскольку по-гречески «таматархес» означает «командир полка», имя сохранило свое изначальное значение даже в эллинизированной форме. В византийских источниках Таматарха упоминается начиная с VIII в.
