Нашествия татар, начиная с XIII века, оказались разрушительными для многих крымских городов: Эски-Кермен практически перестал существовать, Чуфут-Кале стал главной крепостью татар. Не избежал разрушений и Мангуп, но при этом он все же сумел отстоять свою самостоятельность. В середине XIV века здесь возводятся укрепления, строится княжеский дворец, восстанавливается большая базилика святых Константина и Елены, укрепляется цитадель, о чем свидетельствуют скупые строки надписи, где впервые употреблено название «Феодоро». В этот период зависимость Крыма от Золотой орды, раздираемой усобицами, ослабела. В год Куликовской битвы хан Тохтамыш заключил с генуэзцами договор, согласно которому за ними закреплялось Южное побережье от Чембало (Балаклава) до Солдайи (Судак). Эта зона, называемая «капитанством Готия», явлалась предметом постоянных конфликтов между Феодоро и Кафой (Феодосией). Горная же часть Крыма, с Феодоро в центре, осталась самостоятельной, находясь лишь в вассальной зависимости от самого хана.
В XV веке княжество занимало заметное место в истории Крыма и соседних с ним областей. Этот период гораздо лучше освещен письменными источниками и археологическими памятниками. Они свидетельствуют о связях Феодоро с Москвой, о соперничестве его князей с генуэзцами за контроль над морской торговлей. Интересно, что в русских бумагах княжество Феодоров именуется часто просто «сторона Федоров», что тоже явно не случайная описка...
Некоторые историки считают, что основа княжества могла сложиться еще в конце XII века. Есть предположение, что князья Феодоро происходят от знатного армянского рода Гаврасов, княживших с Х века во внутренних областях Понта (когда-то принадлежавшего Митридату) и позднее включенных в состав Трапезундской империи Комнинами. Высказывалось также предположение, что представители Гаврасов появились в Херсонесе уже в XII веке в качестве византийских наместников-топархов. Теснимые турками, с которыми они вели давнюю упорную борьбу, отстраненные от власти Комнинами, Гаврасы вполне могли отправиться в провинцию, тесно связанную с их бывшими владениями, – Тавриду, в XIII веке уже практически независимую. Предположение это опирается на свидетельство русской летописи, где упоминается Степан Васильевич Ховра, «князь Готии», который эмигрировал в Москву в 1391 или 1403 году. Здесь он принял монашество под именем Симон, а сын его Григорий основал монастырь, названный в честь отца Симонов. Фамилия Гаврасов долго сохранялась среди выселенных греков Азовского побережья, и в форме Габрас – в окрестностях Трапезунда; до недавнего времени сохранялось название села Гавры близ села Соколиного на реке Бельбек.
Из того, что известно о предыдущей истории рода, можно предположить, что Гаврасы привезли с собой на Русь героические воспоминания о многовековой борьбе с турками, культ святого Федора – князя, погибшего смертью храбрых в этой борьбе в 1098 году, признанного православной церковью мучеником в XII веке и святым – в XIV веке, героя греческой и турецкой народной поэзии.