Церковь Святых Архангелов Михаила и Гавриила (Сурб Рештакалетац) является одним из сохранившихся на территории Феодосии памятником армянской средневековой архитектуры. Она напоминает итальянские храмы Средневековья, при этом сохраняя все характерные черты армянской средневековой архитектуры. Армяне-католики имели право строить свои церкви в генуэзской части Кафы, так как обладали равными правами с генуэзскими гражданами города, поэтому архитектура сооружения близка к архитектуре аналогичных церквей Италии.
Священники храма Святых Архангелов Михаила и Гавриила участвовали во Вселенском соборе 1438 года, который закрепил унию армянской и римско-католической церквей. Само здание церкви Святых Архангелов Михаила и Гавриила является своеобразной интерпретацией сооружения армянской культовой архитектуры ХІІ века в деревне Птгни близ Еревана.
Сохранившаяся надпись гласит: «Сей храм построен во имя небесных воинов Гавриила и Михаила, служителей Бога Слова, на праведные средства Аствацатура, супруги Ахут-Хатун Садата и Хатун, детей Хачатура, Леона, Иоанесса, Магсуди, Мелика лета 857 года», то есть в 1408 году.
Армянскую церковь Святых Архангелов Михаила и Гавриила возвели в 1408 году, используя в качестве материала распространенный в Крыму бутовый камень, местами тесанный. Снаружи стены храма оштукатурены раствором из цемянки.
На северо-западном углу сооружения установлена шестигранная звонница из камня, украшенная резьбой. Снаружи здание имеет вид латинского креста. На западной стене у входа в храм Святых Архангелов Михаила и Гавриила сохранилось рельефное изображение Божьей Матери. Внутри церкви едва заметны остатки росписи. Еще в 90-е годы XIX века над куполом церкви возвышался позолоченный крест.
Внутреннее убранство церкви Святых Архангелов Михаила и Гавриила было очень богатым и живописным. Церковь имела свой скрипторий, где писались церковные книги.
осле революции ее, как и многие другие армянские храмы, закрыли.
В 1967-1970 годах храм Святых Архангелов Михаила и Гавриила был реставрирован: восстановлены утраченные конструкции, произведена инъекция трещин, заменены окна, двери, черепичное покрытие крыши.
Церковь Архангелов Михаила и Гавриила была занесена в список памятников архитектуры в соответствии с постановлением Совета Министров УССР от 24.08.1963 года №970, уч. №269-274; и решением Крымского облисполкома от 22.05.1979 года №284.
Сейчас церковь Архангелов Михаила и Гавриила не работает, она находится в аварийном состоянии. В 1968 году, когда была реставрация, купол восстановили неправильно, и теперь он сильно расходится. Храм нуждается в реставрации.