Своим архитектурным обликом храм схож с армянскими церквами XIII-XIV веков:
квадратное в плане здание, увенчанное куполом на восьмигранном барабане с узкими окнами. Позже церковь перестраивалась:
со стороны главного входа пристроили довольно вместительное помещение, разделенное столбами на три нефа, перекрытых сводами с опирающимися на консоли арками. Благодаря этому храм мог принимать большее количество прихожан. Минуя мрачноватую пристройку, верующие попадали в высокий, светлый купольный зал. Он был замечательно украшен: по бокам полукруглой апсиды стояли в полный рост фигуры Иоанна Крестителя и Николая Чудотворца, вырезанные из камня. Торжественные, освещенные солнечным светом, они производили на посетителей неизгладимое впечатление. В верхней части апсиды находилось изображение Христа и двенадцати апостолов.
Время безжалостно к строениям, но еще в конце XIX века епископ Таврический и Симферопольский Гермоген видел внутреннее убранство церкви таким:
«В церкви замечательны древние, выбитые на стенах изображения: на горнем месте — Спасителя, а по сторонам Его — 12 апостолов, по 6 на каждой, над жертвенником — Иоанна Крестителя с агнцем на руках, на южной стене — святителя Николая Чудотворца с книгою в руке, под куполом — лик Господа, близ входа в храм на северной стороне — святого великомученика Георгия на коне. Храм небольшой, но очень прочен».
Храм был расписан удивительно красивыми фресками, фрагменты которых сохранились до наших дней. В 1927 году средневековые храмы Феодосии осматривала реставрационная комиссия, в состав которой входил русский художник и искусствовед И.Э. Грабарь. Он предположил, что некоторые фрески храма Иоанна Предтечи принадлежат кисти знаменитого византийского живописца Феофана Грека, выдающегося мастера фрески, иконописи, миниатюры. В 70-е годы XIV века он работал в России. Сохранились выполненные им иконы в Благовещенском соборе в Москве и фрески церкви Спаса-на-Ильине в Новгороде.
С храмом Иоанна Предтечи связано еще одно историческое событие, еще одно имя. Осенью 1474 года в Кафу прибыл русский путешественник Афанасий Никитин, возвращавшийся на родину в Тверь из далекой Индии. В «Хождении за три моря» он писал: «Море перешли, да занесло нас к Балаклаве, и оттуда пошли в Гурзуф, и стояли мы там пять дней. Божиею милостью пришел я в Кафу за девять дней до Филиппова поста. Милостию Божией прошел я три моря». В то время причал и главные ворота города находились у генуэзской крепости. Тому, что произошло после, нет документальных подтверждений, но предание утверждает, что Афанасий Никитин увидел церковь Иоанна Предтечи и услышал пение молитв. Поскольку отважному путешественнику долгое время пришлось жить среди людей, исповедовавших буддизм и мусульманство, то он с радостью молился в храме, благодаря Бога о своем благополучном возвращении.
В 1475 году Кафу захватили турки. Мусульманская религия стала основной, хотя в многонациональном городе действовали храмы разных религиозных конфессий. Но, очевидно, с течением времени церковь Иоанна Предтечи пришла в запустение, изменилось и ее название, теперь она стала Карантинной. В 1887 году епископ Таврический и Симферопольский Гермоген писал: «Карантинная церковь, из дикого камня, в честь иконы Иверской Божьей Матери — в юго-восточной часть Феодосии, в Карантинной слободке, населенной большею частью отставными нижними военными чинами и рабочими. Время постройки церкви неизвестно, но, несомненно, она существует со времени владычества генуэзцев в Феодосии. Священник Карантинной стражи Николай Трегубов с помощью благотворителей возобновил ее в 1858 году и освятил 31 августа. В 1875 году Рукавишников окрасил ее и пожертвовал три иконы в киотах за стеклом». Храм был освящен в память Иверской иконы Божией Матери.
В этом храме в 1906 году венчались Константин Федорович Богаевский и Жозефина Дуранте. К. Ф. Богаевский, известный русский художник-«киммериец», родился в Феодосии и жил в Карантине, здесь же находилась его мастерская. Храм иконы Иверской Божией Матери был его любимым. В грозные революционные годы рядом с храмом были расстреляны около 7000 белых солдат и офицеров.
В 30-е годы XX века храм был закрыт и фактически заброшен. Несмотря на то, что в советское время на Карантине создали историко-архитектурный заповедник, который охранялся законом, храм начал разрушаться и едва не погиб. Из-за споров между проектным институтом и органами архитектуры реставрационные работы не велись семь лет. Тем временем вода через дыры в прохудившейся крыше залила стены и повредила древние фрески, пол был покрыт грудами мусора и мокрого грунта. Слава Богу, что нашлись неравнодушные люди — архитекторы, искусствоведы, музейные работники, которые смогли убедить власти в необходимости срочно спасти храм. Реставрационные работы консультировал архитектор и скульптор Валерий Замеховский. Были проведены дренажные работы, уровень земли понизили на 60-70 сантиметров, церковный двор вымостили камнем. Помогали и будущие прихожане храма, они выносили из церкви мусор, украшали двор цветниками. Реставрация храма закончилась в 1996 году, и он был возвращен верующим.
