Первое поселение, а точнее торговая фактория на территории современной Феодосии была основана в VI веке до н.э. купцами-мореходами, выходцами из древнегреческого города Милета. Примечательно то, что это именно им принадлежит авторство названия города Феодосия (в переводе – «дар богов» или «Богом данная»), возникшее в V веке до н.э. Боспорское царство пожелало расширить свои земли за счет древнегреческого на то время уже полиса. Длительная война закончилась тем, что в 355 году до н.э. город был включен в состав державы-завоевателя, которая сделала его своей крупнейшей гаванью, экономическим центром. Такое процветание Феодосии продолжалось несколько веков, пока в VI н.э. она не была разрушена гуннами. На месте некогда процветающего полиса появилось небольшое поселение аланов Ардабра (в переводе – «семибожная»). В V веке оно перешло под влияние христианской Византийской империи. В конце VII века в Ардабру вторгаются хазары, однако со временем господство Византии возобновляется. Былая значимость полиса от разрушительных нападений различных народов утрачивается. Несколько веков он существует как небольшое селение, пока в XIII веке в период раннего Средневековья на его месте не появляется более крупный поселок, подчиненный золотоординцам, под названием Кафа. К концу того же века ее приобретают у татарского хана генуэзские купцы, которые сохраняют название и владеют землями у побережья Феодосийской бухты на протяжении двух столетий. Опасаясь татарских набегов, генуэзцы возводят мощные крепости, развалины которых можно и сейчас увидеть в черте города.

В 1475 году Кафа пала под натиском турков-османов, которые переименовали ее в Кефе и превратили в крупный пункт международной торговли.

Во время русско-турецкой войны в 1771 году город был взят приступом российскими войсками. После посещения его императрицей Екатериной II  в 1787 году он был включен в состав Таврической губернии. Однако былая слава торгового центра уже на то время канула в лету. Так продолжалось довольно долго. На протяжении века кардинальных изменений город не переживал. Только в 1804 году ему вернули древнее название Феодосия.

Новому этапу развития Причерноморского города сопутствовало проведение в 1892 году железнодорожной ветки из Джанкоя и строительство в 1899 году морского порта.

В начале ХХ века Феодосия, как и весь Крым, переживала тяжелые годы кровопролитной братоубийственной гражданской войны, пока в ноябре 1920 года здесь не утвердилась окончательно советская власть. Город зажил славу крупного промышленного, курортного и культурного центра Крымской АССР.

Великая Отечественная война стала тяжелым испытанием для Феодосии. С ноября 1944 года она была оккупирована немецко-фашистскими захватчиками. Ее участие в войне правительство отметило орденом Отечественной войны I степени на знамени города.

По окончании войны Феодосия вновь возрождается. Основные ее силы были направлены на развитие промышленности. Как город-курорт Феодосию по достоинству оценили только в 70-х годах ХХ века, когда присвоили ей такой статус.

В разное время Феодосию посещали И.К. Айвазовский, М.Л. Цветаева, М.А. Волошин и другие писатели, художники и ученые. Ныне о пребывании И.К. Айвазовского в городе может много поведать Феодосийская картинная галерея имени И.К. Айвазовского.