Feodosija ir viena no senākajām zināmajām pilsētām Ukrainā. Pilsētu 6. gadsimtā p.m.ē. dibināja sengrieķu kolonisti no Milētas un tās senais nosaukums bija Teodosija (grieķu: Θεοδοσία). Mūsu ēras 4. gadsimtā to nopostīja huņņi. Līdz pat 13. gadsimtam Feodosija bija neliels ciematiņš, kurš kādu laiku bija hazāru, bet kādu laiku Bizantijas ietekmē. Līdz ar pārējo Krimu tā nokļuva kumānu varā, bet 1230. gados ieņēma mongoļi. 13. gadsimta beigās Feodosiju no Zelta ordas iegādājās Dženovas tirgotāji, nosaucot par Kafu (Caffa vai Kaffa). Tā kļuva par vienu no lielākajām ostas pilsētām Melnajā jūrā un par svarīgu vergu tirdzniecības centru. Tiek uzskatīts, ka no Kafas 1347. gadā ar dženoviešu tirgotājiem Eiropā ieviesās Melnā nāve. 1380. gadā Kafā nogalināja Zelta ordas karavadoni Mamaju.
1475. gadā to iekaroja Osmaņu impērijas karavadonis Džediks Ahmeds-pašā. Ar Kefes (Kefe) nosaukumu tā bija viena no svarīgākajām ostām Melnajā jūrā. 1783. gadā cietoksni un ostu pakļāva Krievijas Impērija un 1802. gadā to pārdēvēja vecajā grieķu vārdā par Feodosiju (Феодосия). Otrā pasaules kara laikā Feodosijā notika sīvas kaujas un tā tika stipri nopostīta. 1954. gadā Feodosiju iekļāva Ukrainas PSR sastāvā. 2006. gadā pilsētā notika masu protesti pret ASV karavīru ierašanos.