По благословению владыки Алексия 17 сентября 1862 г. был образован строительный комитет, который должен был изыскать средства и приступить к постройке храма при источнике. Комитет состоял из настоятеля Кизилташской киновии игумена Парфения (убитого татарами 22 августа 1866 г.), священника из с.Салы (ныне с.Грушевка) Иоанна Новицкого, кишлавского церковного старосты Иова Узунбеева и кишлавского дьячка Стефана Михо. Игумену Парфению выдали из консистории сборную книжку для пожертвований, а дьячок Михо должны был смотреть за строительным материалом.
Средства для строительства церкви были собраны очень быстро, и уже в мае 1863г. строительный комитет приступил к сооружению храма, который был построен в невиданно короткие сроки, почти за два месяца, и к 22 июля того же года был полностью закончен. Строительство осуществилось так стремительно благодаря необыкновенной энергии и хозяйственной деятельности кизилташского игумена Парфения. Он создал в короткий срок из убогой киновии процветающую обитель во имя св. Стефана Сурожского, и теперь по благословению владыки Алексия помогал новому монастырю, часто приезжая сюда верхом через горы из Кизилташа. Первая монастырская церковь во имя св. преподобномученицы Параскевы – в какой-то мере памятник игумену Парфению, принявшему мученическую кончину от рук убийц.
Храм вышел небольшим, площадью всего 5 кв. саженей, но этого на тот период было достаточно. Он был окружен крытой галереей, где стояли молящиеся. Пол в храме был деревянный, а в галерее – глиняный, монахини ремонтировали его каждую неделю, гладко заделывая трещины и выбоины. Высокопреосвященный Алексий распорядился, чтобы в церковь были переданы церковная утварь, священнические облачения и колокол весом в 12 пудов, из вещей, собранных странником Андроником, впоследствии иноком Кизилташской киновии. Два других колокола строительный комитет приобрел в Симферополе. Одежда на престол и жертвенники была выдана из архиерейской Крестовой церкви.
В день памяти св. преподобномученицы Параскевы, 26 июля 1863 г., Владыка Алексий при большом стечении народа торжественно освятил вновь сооруженную церковь, и с того дня в ней начались богослужения.
В 1887 году, по благословению владыки Мартиниана, церковь перестроили и увеличили по плану, составленному гражданским инженером Агиенко. Сквозную галерею, окружавшую храм, обнесли каменной стеной и непосредственно соединили с церковью. 24 июля 1888г. преосвященный Мартиниан вновь освятил перестроенный храм. В том же году к церкви пристроили новую каменную колокольню, крытую железом; кресты с шарами на церкви и колокольне были вызолочены. Заново отделали и иконостас в храме: выкрасили светло-розовой краской и позолотили. Перед клиросами устроили два боковых небольших иконостаса, также крашенных с позолотою. На устройство этих иконостасов Т.И.Мальчевская пожертвовала 300 рублей.
В советское время храм, как и весь монастырь, был закрыт, сильно пострадал. В годы возрождения обители в храме проведены восстановительные работы, стены украсили росписи, в храме ведутся Богослужения.