Храм расположен в восточной части крепости. Впервые в литературе описан в 1642 г. и назван мечетью Айя-Баязид.  На русском плане 1771 г. назван Падиша-мечетью. Археологические исследования проводились в 1926, 1969-75 и 1986 гг.
Храм  представляет собой единовременную постройку третьей четверти XIV в. Основной объем выполнен в форме куба с каменным сферическим сводом на тромпах. С севера к нему примыкает притвор, отделенный тремя арочными пролетами. С востока к зданию пристроена открытая трехчастная аркада, в которую из помещения ведут дверь и два окна, обрамленные резьбой. Конструкция   здания   имеет   многочисленные аналоги в мусульманской культовой архитектуре Малой Азии и а этого периода. Работы по декору здания не были полностью завершены. Этому помешал, очевидно, захват города генуэзцами в 1365 г. В 1373 г. здание было оштукатурено и расписано изнутри. Над михрабом появилась строительная латинская надпись: «Во имя Христа Аминь 1373 г. дня четвертого января это сооружение повелел возвести господин Каталани Христос спаси». Под надписью гербы Каффы, Генуи и рода Каталани. В генуэзский период (1373-1475 гг.) здание использовалось как католический собор — центр небольшого монастыря. Внутри постройки на стенах и колоннах сохранились остатки фресок с изображениями христианских святых с латинскими   надписями, а также многочисленные граффити: надписи, изображения кораблей и щитов с гербами. После 1475 г., когда вошел в состав Османской империи, здание использовалось в качестве мечети. С конца XVIII в. использовалось как гарнизонная часовня для  расквартированного в Судаке контингента войск Российской империи; некоторое время после 1827 г. — как лютеранский молельный дом немцев-колонистов, чей поселок   примыкал   к   крепостным   стенам   с   северо-западной стороны (сейчас пос. Уютное), а с 1883 г. до 1926 г. — как армяно-католический собор. В настоящее время в здании расположен музей историко-архитектурного заповедника «Судакская ».