История создания церквей в Алуште начинается с 1833 года, со времени утверждения проектов, представленных на конкурс. Судя по документам, сохранившимся в государственном архиве Крыма, высочайшее утверждение получили проекты, предоставленные генерал-губернатором Новороссии графом М.С. Воронцовым, разработанные известным Одесским архитектором Г.И. Торричелли (1796-1843).

За строительство церквей в Ялте и Алуште взялся Керченский купец I гильдии Карл Томазини, «имевший ранее большие подряды по постройкам зданий и церквей в губерниях Новороссийского края». Причем, в Алуште строил церковь его брат - Иван Томазини. Руководил строительством церквей в Алуште и Ялте (речь идет о церкви Иоанна Златоуста на Поликуре архитектор Южного берега Крыма, сменивший Эльсона в 1834 году, Я. Колодин. Вместе с ним в строительстве принимали участие архитекторы Эшлиман и Дево. Церковь построена была, как утверждают специалисты-искусствоведы, по типу сельских церквей Англии, с использованием готической архитектуры, как в фасадах, так и в интерьере.

Для архитектуры 20-40-х годов XIX века в России было характерно романтическое направление эклектики с использованием элементов готики. Торричелли использует ряд приемов, характерных для готических костелов; щипцовое завершение боковых приделов (это можно увидеть и сейчас), колокольня с пирамидальным шатровым завершением (не сохранилась), стрельчатая форма оконных и дверных проемов (сохранилась), окна украшали цветные витражи. Судя по старым фотографиям и гравюрам с видами Алушты, колокольня храма служила градостроительной доминантой всего города.

Иконостас был выполнен мещанином Черниговской губернии Пантелеймоном Бочаровым. Кроме иконостаса храм украсили «двадцатью праздничными иконами по 20 руб. каждая, на досках квадратно в Уз аршина каждая». В 1841 году по чертежам губернского архитектора С. Дево вокруг церкви была возведена прямоугольная металлическая ограда на каменных столбах. Таврическая епархия подчинена была архиепископу Херсонскому и Таврическому Гавриилу, который назначил освящение церкви нашей и священника.

Как видим, церковь во имя Феодора Стратилата была освящена 30 ноября 1842 года. И это не случайно: ведь в этот день Святая церковь празднует память Андрея Первозванного, с именем которого в Тавриде много связано. Первым священником был протоиерей Михаил Родионов. Очевидно, человеком он был умным, и честным, и благостным, ибо уже в 1851 году был благочинным Крымских церквей.Процветала вплоть до революции.