През 705 г. Юстиниан II Ринотмет, императорът с отрязания нос, бяга от заточение в Херсон, намиращ се на Кримския полуостров, и след много перипетии се озовава при Тервел. Двамата сключват сделка - Юстиниан с помощта на 15 000 българи стига до Константинопол и след преврат си връща короната. Тервел получил областта Загоре(още - Загора), луксозни дарове (според легендата, Юстиниан накарал Тервел да забие копието си в земята и да опре на него щита си. После византийцити насипвали върху тях злато и скъпоценности докато ги покрили изцяло) и титлата кесар. Тази титла, втора в империята и запазена за престолонаследника, направила българския владетел практически равен на василевса в очите на ромеите, което влошило и без това незавидния престиж на императора. Никога дотогава ,а и никога след това тази титла не била давана на чужденец, а и по този начин хан Тервел вече получил правата на легитимен владетел над територии, които доскоро били собственост на Византийската империя. Изглежда Юстиниан допуснал този пропуск в имперската доктрина, притиснат от обстоятелствата. Когато се почуствал сигурен на престола той организирал поход срещу българите, но бил разбит през 708 г. край Анхиало (днес се нарича Поморие). След убийството на Юстиниан през 711 г. Тервел продължил да се намесва в работите на Империята, под предлог че отмъщава за съюзника си. През 716 г. сключил мирен договор с новия император Теодосий III. Договорът съдържал и търговски клаузи. По времето на хан Тервел е създаден барелефът Мадарски конник в чест на победите на Тервел над Византия.