Свое современное название город получил еще в античные времена. В переводе с древнегреческого Феодосия означает «Богом данная». С 2015 года городу присвоено почётное звание «Город воинской славы».
Античный период
История Феодосии начинается в античные времена с небольшого греческого поселения 6 века до н.э. Колонизацию местного побережья начали купцы древнегреческого города Милета. Довольно быстро небольшая фактория, благодаря своему выгодному географическому расположению, превратилась в процветающий город, активно торгующий с заморскими странами, окрестными племенами и городами-государствами.
Зародившееся недалеко от Феодосии Боспорское царство не оставило незамеченным такой лакомый кусок, и в 4 веке до н.э. город был захвачен соседями, воспользовавшимися помощью своих союзников скифов. Войдя в состав Боспора, Феодосия становится одним из значимых городов царства, вторым на европейской части после столицы Пантикапеи.
Последующие 300 лет город переживал эпоху экономического подъема и культурного процветания, население выросло до 8000 человек. Но на рубеже тысячелетий началась эпоха увядания греческих колоний в Крыму. Боспор сначала стал частью Понтийского царства, а затем оказался под властью Рима.
Череда войн и смены властителей не могли не сказаться на благополучии торгового города. Окончание античной истории Феодосии произошло после вторжения в Крым в IV веке гуннов. Кочевники полностью разрушили город и в течение последующих 100 лет на его месте находилось лишь небольшое аланское поселение Ардабда.
Византийский и хазарский периоды не принесли Феодосии ничего, кроме полного забвения. Даже маленькая Ардабда была разрушена хазарами.
Генуэзский период
Возрождение города началось в XIII веке, когда генуэзцы выкупили побережье Феодосийского залива у захвативших к тому времени Крым кочевников Золотой Орды. Новые владельцы основали здесь торговое поселение, для защиты которого возвели мощную крепость и дали ей имя Кафа.
Колония генуэзцев вскоре превратилась в процветающий город, в который благодаря его выгодному географическому положению стекались богатства Северного Причерноморья, Золотой Орды, Кавказа и Руси. Основным и самым дорогим товаром, которым торговала Кафа, были рабы.
В начале XIV века город стал главным генуэзским центром в Крыму. К 1320 году в нем проживало около 70.000 человек. В этот период город даже начал чеканить собственные монеты.
Для защиты накопленных богатств и с моря, и с суши активно строились фортификационные укрепления. Крепость на тот момент стала самой крупной в Европе: она имела 30 башен и 6 ворот. Все они были соединены между собой стенами общей длиной около 6 км, их высота достигала 11 метров, а толщина была около 2 метров.
В генуэзский период Кафа была многонациональным городом. Здесь в согласии проживали итальянцы, греки, русские, татары, армяне, караимы, евреи, черкесы, венгры, болгары. Разноязыкое население возводило здесь католические, армяно-григорианские, православные церкви, мечети, синагоги и кенассы. От генуэзского периода в городе сохранилось восемь христианских храмов и одна мечеть.
Средние века
В средневековой Феодосии случались события, значительно влиявшие на общеевропейскую историю.
Так в 1345 году золотоордынский хан Джанибек, несмотря на мирные договоренности, с большим войском осадил крепость. С помощью катапульт он забросал город трупами своих зараженных чумой воинов. В Кафе вспыхнула эпидемия, вынудившая большое количество генузцев покинуть ее и вернуться на родину в Геную. По всему пути их следования вспыхивали очаги заболевания. В итоге чума унесла жизни около 80 млн. человек — четверть населения Европы.
Битвы с ордынцами, падение Константинополя в 1453 году и блокирование турками Босфора привели к потере Кафой былого торгового значения. Однако после захвата Крыма османами в 1475 году теперь уже Кефе начала возрождаться и быстро стала центром торговли в Северном Причерноморье. Здесь находился крупнейший невольничий рынок, где ежегодно продавались тысячи рабов, захваченных крымскими татарами во время набегов на русские, украинские и польские земли.
В турецкий период, подчеркивая важность и большое население, город называли «Малым Стамбулом». При этом он не потерял свою многонациональность. Продолжали действовать храмы различных конфессий. В Кефе находился центр православной Готско-Кефайской епархии. Тем не менее при турецком владычестве значение города понемногу снижалось, в течение трех веков он сильно обезлюдел.
В составе России
Круг переименований города Феодосия — Ардабда — Кафа — Кефе замкнулся после присоединения Крыма к России в 1783 году. Феодосии вернулось ее первоначальное имя, данное в период зарождения.
В первые десятилетия в составе Российской империи город находился в упадке и начал развиваться только к середине XIX века благодаря богатым меценатам и экономической политике властей. Началось строительство торгового порта в соответствии с указом Александра III. Усилиями фабрикантов в городе начала развиваться промышленность.
После Крымской войны 1853−1856 гг. в Феодосии действовали чугунолитейный, гвоздильный, два кирпично-черепичных, известковый, водочный заводы, развивались виноделие и рыбный промысел.
Известный в те времена промышленник и благотворитель Иосиф Вениаминович Стамболи, продолжая дело своего отца, развивал крупнейшую в Крыму табачную фабрику. Предприниматель на собственные средства строил в городе дома своим рабочим, организовывал для них бесплатную медицинскую помощь, выплачивал стипендии нуждающимся студентам, помогал молодым музыкантам.
Внес Стамболи вклад и в архитектуру города. Благодаря ему в 1914 году в Феодосии появилась дача-дворец фабриканта, являющаяся сегодня одним из самых красивых зданий не только города, но и всего Крыма.
Промышленному развитию и росту города к концу XIX века послужило окончание строительства железнодорожной ветки из Джанкоя, а также перевод в 1899 году из Севастополя в Феодосию коммерческого порта. В итоге к началу XX века Феодосия представляла собой красивый, благоустроенный и оживленный город.
Развивались в городе не только промышленность и порт. С Феодосией связаны жизнь и деятельность многих выдающихся творческих личностей.
Здесь в конце 90-х годов XIX века учился в гимназии будущий выдающийся поэт, художник, художественный и литературный критик Максимилиан Волошин.
В Феодосии с 1924 по 1930 год жил и работал русский писатель-прозаик и поэт Александр Грин. В эти годы он написал роман «Золотая цепь» и закончил главный свой шедевр — роман «Бегущая по волнам».
Самым выдающимся феодосийцем был великий художник-маринист Иван Константинович Айвазовский, который родился в городе в 1817 году. В течение своей жизни он много путешествовал, но о родном городе никогда не забывал и всегда считал его своим домом.
Кроме занятий живописью, Айвазовский занимался благоустройством Феодосии. Благодаря и его усилиям небольшой уездный городок стал одним из красивейших и развитых городов не только Крыма, но и северного Причерноморья. Он открыл здесь школу искусств и картинную галерею, был инициатором строительства железной дороги Феодосия—Джанкой и крупнейшего в Крыму торгового порта.
Айвазовский подарил городу, страдавшему от безводья:
…в вечную собственность 50 000 ведер в сутки чистой воды из принадлежащего мне Субашского источника.
От источника в имении Айвазовских в город был проложен водопровод с бесплатной для горожан водой. В благодарность за этот дар феодосийцы установили в честь семьи Айвазовского фонтан-памятник «Доброму гению», который можно увидеть и сегодня в парке Юбилейный.
В XX веке Феодосия пережила Гражданскую войну, оккупацию немецко-фашистскими захватчиками и освобождение советскими войсками 13 апреля 1944 года. Яркой страницей в военной истории города стал феодосийский десант в ходе Керченско-Феодосийской десантной операции 1941−1942 гг., что в значительной степени облегчило оборону Севастополя.
В ночь с 28 на 29 декабря 1941 года с кораблей Черноморского флота в акватории феодосийского порта высадились специальные штурмовые отряды, которые обеспечили плацдарм для основных сил, к концу дня 29 декабря захвативших город. Всего за 8 дней операции советские войска отбили весь Керченский полуостров и удерживали его до середины мая 1942 года. Правда, Феодосия пала в результате контрнаступления немецких войск еще 17 января 1942 года.
Экономическое развитие города в начале ХХ века обеспечивал не только торговый порт, который, тем не менее, играл в этом видную роль. К 1941 году в Феодосии насчитывалось 20 промышленных предприятий, несколько научных учреждений, в которых работали многие видные ученые, в том числе будущий академик
Тогда же, в 20−30 годы, началось бурное развитие феодосийского курорта, становление которого произошло еще в первой половине XIX века. Весной 1921 г. дача 
Современная Феодосия — климато-бальнеологический курорт с большим количеством пляжей, грязелечебниц, санаториев и домов отдыха. Кроме туризма, здесь развивается винодельческая, пищевая, лёгкая промышленности, машиностроение, сельское хозяйство и рыболовство.