Церковь расположена в районе Карантина, рядом с другими православными храмами Иоанна Богослова,
Святого Георгия, Святого Димитрия, неподалеку от средневековой генуэзской цитадели.

В некоторых путеводителях эта церковь именуется храмом Иоанна Предтечи.
На одной каменной плите, найденной во время реставрационных работ в храме, была обнаружена
высеченная в камне дата "1348", ее и взяли за отсчет времени строительства храма.
В нервом плане города Кафы, составленном в 1784 году русскими картографами,
на Карантине было обозначено 11 церквей, тогда как в 1660 году известный западно-европейский
ученый и путешественник Боплан насчитал в Кафе 22 армянских, 12 греческих храмов и
соборную церковь Св. Петра. А Устав генуэзских колоний 1449 года упоминает до 20-ти
латинских церквей, несколько монастырей.

Русское православное население Кафы имело свою церковь. Архиепископ Таврический Гавриил,
описывая христианские древности в Феодосийском уезде
(ЗООИД - Записки Одесского общества истории и древности - 1844 г.) среди 17 наболее
известных и древних храмов Феодосии не называют описываемую в церковь именем Иоанна Предтечи.
В перечне древних храмов под номером 17 у него значится церковь "во имя Успения честныя главы
Иоанна Предтечи в Двухякорной бухте на холмистом мысе" (современный поселок Орджоникидзе).

Позже, в 1887 году, Епископ Симферопольский и Таврический Гермоген в своем фундаментальном
труде по истории Крыма и христианства в Крыму о православных храмах пишет:
"... Карантинная церковь из дикого камня, в честь Иверской иконы Божией Матери,
в юго-восточной части Феодосии в Карантинной слободке ... священник карантинной стражи
Николай Трегубов с помощью благотворителей возобновил ее в 1858 году и освятил
31 августа. В 1875 году Рукавишников окрасил ее и пожертвовал три иконы в киотах за стаклом:
Воскресенье Христово, Рождество Христово и Вознесение Христово. (Гермоген. 1887:379).

По опсанию историка М.П.Погодина, посетившего Феодосию в 1871 году, в церкви
Иверской иконы Божией Матери находились образа Божией Матери,
праведных Захарии и Елизаветы возле жертвенника, образ святого, переносящего спеленатое дитя.
В настоящее время местонахождение этих икон не установлено.

Судя по сохранившемуся архитектурному облику первоначально церковь Иверской иконы Божией Матери
в плане была квадратной. Главу ее венчал восьмиугольный купольный барабан с узкими окнами.
Несколько позже, когда увеличилось число прихожан, а в XIX веке их было болеедвухсот,
с западной стороны пристроили еще одно помещение - притвор со створчатым перекрытием
на четырех столбах. Поражали прихожан и всех, кто посещал храм, благолепное
убранство внутри, рельефные изображения, иконы Спасителя, Пречистой Девы Марии, святых.

"В церкви замечательные древние, выбитые на стенах избражения на горнем месте
Спасителя, а по сторонам его - двенадцать апостолов, по шесть на каждой,
над жертвенником - Иоанна Крестителя с агнцем в руке, на южной стене - святителя
Николая Чудотворца с книгой в руке, под куполом - лик Господа, близ входа в храм на
северной стороне - святого великомученника Георгия на коне". (Гермоген. 1887:379)

О величественном убранстве храма говорят остатки художественной росписи
на евангельские темы свода, купола и стен, которые, к сожалению не созранились.

Русская Православная Церковь совершала в этом храме службы для служащих карантинной стражи,
рабочих, воспитанников учительского института и прихожан этого района.

Существует предание о том, что знаменирый русский купец и путешественник Афанасий Никитин,
возвращаясь в родну Тверь из "хождений за три моря", в 1472 году приплыл в Кафу и в этом
храме отслужил благодарственный молебн о благополучном исходе своего путешествия.

В 1906 году в церкви Иверской иконы Божией Матери известный художник романтической
Кимерии Константин Богаевский венчался с племянницей городского головы Жозефиной Дуранте.

Еще в начале XX века на территории церкви с южной стороны находилось небольшое
православное кладбище, в фамильном склепе на этом кладбище был похоронен
сподвижник генералиссимуса А.В. Суворова, его личный адьютант, участник
знаменитого перехода через Альпы и Отечественной войны 1812 года
Христофор Афанасьевич Анастасьев. В последние годы своей жизни он возглавлял Феодосийскую
таможню, был градоначальником. Здесь же находилась могила и памятник
Кондратия Кондратьевича Штофрегена, участника Крымской войны 1854-1856 годов,
который в 1872-1873 годах был начальником Феодосийского таможенного округа.
На этом кладбище были захоронения и других почетных граждан, однако
кладбище было разрушено, памятники сресены, места захоронений утрачены.

Долгие годы церковь была закрыта и находилась в запустении.
После ремонта и реставрации, которые консультировал и лично проводил
архитектор и скульптор Валерий Зенонович Замеховский, церковь с
января 1996 года начала новую жизнь.

В храме имеются святыни: икона Божией Матери Касперовская и
Чудотворная икона Святителя Пантелеймона с частицами его мощей.

В 1999 году при описании памятников старого кладбища известный
крымский краевед Лихотворик Ростислав Степанивич обнаружил
памятник с надписью:
"Здесь покоится прах священноиерея Николая Захарьевича Трегубова, скончавшегося 27 апреля
1870 года на 52 году, священнодействовавшего в Карантинной церкви. Мир праху твоему".
Валерий Замяховский и здесь принял активное участие в реставрации,
а священники благочиния во главе с о.Михаилом отслужили панихиду по первому иерею Иверского храма.