Церковь Иверской Божьей Матери является древнейшей церковью Феодосии. Она построена в 1348 году около стены Генуэзской крепости Кафа в армянском квартале города. Всего в этом квартале было пять церквей, четыре из которых сохранились до наших дней. Руины пятого храма найдены во время раскопок.
Население Кафы во время владычества генуэзцев на 2/3 состояло из этнических армян. После строительства внешних стен Генуэзской крепости Кафа часть армян основали свою коммуну и поселились около восточной стены. Позже они обнесли свою коммуну стеной и этот квартал назвали Айоц Берд (Армянская Крепость). Здесь они построили пять церквей, Церковь Иверской иконы Божьей матери – самая большая из них.
После завершения строительства армянскую церковь освятили в честь Иоанна Предтечи. В 1474 году несколько зимних месяцев в Кафе провел знаменитый русских путешественник и мореплаватель Афанасий Никитин. Он вернулся из путешествия в Индию и отдыхал в городе.
Здесь же он работал над своей книгой «Хождение за три моря». В церкви Иоанна Предтечи он молился, чтобы вернуться здоровым в родную Тверь. Он уехал буквально за несколько месяцев до вторжения турок в Крым. В 1475 году турки взяли штурмом все крепости генуэзцев в Крыму: Кафа, Судак и Балаклаву.
Афанасий Никитин уехал из Кафы с последним русским караваном, но до родной Твери не доехал. Он умер от болезни в Смоленске. В память о пребывании Афанасия Никитина в Кафе и его молитвах в церкви Иоанна Предтечи, рядом с храмом установлен его памятник.
Во время правления Екатерины II армян из Феодосии переселили в низовья Дона, поэтому район Айоц Берд пришел в запустение. Учитывая, что район был огражден стеной, его начали использовать как место для карантина. Все, кто возвращался из азиатских стран были обязаны 40 дней провести в квартале Айоц Берд.
В 1875 году армянская церковь Иоанна Крестители стала православным храмом, который освятили в честь Иверской Иконы Божьей Матери. Сейчас используются оба названия храма: Церковь Иверской иконы Божьей матери и Церковь Иоанна Крестителя. Из-за этого иногда бывают неточности в названиях, тем более что рядом находится Церковь Иоанна Богослова. Иоанн Креститель и Иоанн Богослов – это разные люди.
Согласно древним летописям, фрески в Церкви Иверской иконы Божьей Матери были написаны в 15 веке известным русским живописцем Феофаном Греком. В советское время церковь закрыли и использовали под склад, поэтому древние фрески не сохранились. В России есть только одна церковь, где сохранились фрески Феофана Грека: Церковь Спаса Преображенья на Ильине в Великом Новгороде.