Граф М. С. Воронцов (1782-1856), заботящийся о благоустройстве Южного берега Крыма, решил построить в Алуште большой храм. Подготовить проект будущей церкви он поручил архитектору Торичелли (1796-1843). Она была освящена 30 ноября 1842 года протоиереем ялтинской церкви Сорокиным с благочинным священником Накропиным в честь Феодора Стратилата. Первым священником стал о. Михаил Родионов.

Храм выстроили на средства государства, на церковную утварь было выделено 3316 рублей 55 копеек. Его украсили 20 икон «на досках квадратно в поларшина». Иконостас из липового дерева изготовили на средства мещанина из Черниговской губернии Бочарова.

Храм был построен в готическом стиле и напоминал сельские церкви в Англии. Путеводитель XIX века утверждал, что «главное украшение Алушты составляет красивая православная церковь с колокольней в готическом стиле». Алуштинцы очень любили свой храм, старались сделать его более красивым и благоустроенным, одним из жертвователей был известный промышленник и меценат Н. Д. Стахеев.

В 20-х годах XX века храм претерпел некоторые изменения: к алтарной части пристроили ризницу и пономарню, а также новый престол. Деньги на ремонт и расширение храма собрал священник Сербинов. Храм святого Феодора Стратилата был вновь освящен 6 сентября 1920 года архиепископом Димитрием (Абашидзе).

В алуштинском храме служил священномученик Тимофей Изотов (1875-1938). Он родился и вырос в Симферополе, учился в церковно-приходской школе и любил прислуживать в храме. В 1909 году его приняли в штат кафедрального Александро-Невского собора псаломщиком. В 1912 году Тимофей Изотов был рукоположен архиепископом Димитрием (Абашидзе) в сан диакона. В 1916 году его перевели в Ялту в храм Феодора Тирона, а в 1921 году он стал священником церкви Всех Святых в Симферополе и служил в ней 6 лет. В 1922 году во всех храмах Крыма изымали ценные предметы. Пришлось и отцу Тимофею, скорбя в душе, отдать комиссии все, что потребовали. В 1928 году архиепископ Дионисий (Прозоровский) рукоположил диакона Тимофея в сан иерея и направил в село Новопавловку. Через 8 лет, в сентябре 1936 года архиепископ Порфирий (Гулевич) перевел его священником в алуштинский храм Феодора Стратилата, где он служил до своего ареста.

Прихожане любили своего пастыря за твердую веру, мужество и кротость нрава. Время было тревожное: церкви закрывали, священников арестовывали, верующих преследовали. Община алуштинского храма после церковных служб собирались дома у старосты Матроны Яковлевны Левут. В тайне от посторонних обсуждали церковную жизнь, читали Священное Писание, отец Тимофей совершал молебны и панихиды, крестил детей. Произнося перед членами общины проповеди, с горечью отмечал, что «с приходом советской власти вера в Бога среди населения с каждым днем все падает. Люди даже забывают Церковь и Бога, власть отделила церковь от государства и все время преследует духовенство, религия вообще везде и всюду преследуется. Настало самое тяжелое время. Надо смиренно и терпеливо вести религиозную работу среди населения, нам надо сплотиться».

Но не все смогли выдержать давление властей, две женщины вышли из церковной двадцатки. Это дало законный повод закрыть храм. 8 февраля 1938 года отец Тимофей Изотов был арестован, на допросах держался твердо, виновным себя не признал. Через восемь дней настоятеля алуштинского храма Тимофея Спиридоновича Изотова и председателя церковной двадцатки Гавриила Алексеевича Пасевича приговорили к смерти. В который раз крымская земля обагрилась невинной кровью истинного христианина, до конца пронесшего крест свой и представшего перед престолом Господа вечным молитвенником за нас. Определением Священного Синода Украинской Православной Церкви иерей Тимофей Изотов причислен к лику местночтимых святых.

Трагической оказалась судьба и других священнослужителей: был расстрелян дьякон Никандр Сакун, а отец Петр Сербинов четыре раза оказывался за тюремной решеткой, но по просьбам прихожан выходил на свободу, пока его не сослали. Молились в храме во время Великой Отечественной войны и после установления мира. Двери храма закрылись в 1964 году. В здании устроили клуб «Строитель», при этом его несколько раз перестраивали, колокольню вовсе разрушили, и бывший храм утратил свой первоначальный облик.

Восстановлен он благодаря неравнодушным людям, алуштинцам, которые стараются сберечь исторические и архитектурные ценности своего города. Еще в 80-х годах семья Коробченко, Анна Ивановна и Сергей Тимофеевич, начали обивать пороги высоких кабинетов не только в Крыму, но и в Москве. Они просили восстановить храм в честь святого Феодора Стратилата, уберечь его от полного разрушения. Средства на реконструкцию выделил город, помогали и прихожане.

После проведенной реконструкции храм предстал во всей своей красе. Двери центрального входа украшены богатой резьбой, длинный переход с высокими стрельчатыми окнами по обеим стенам ведет прихожан в центральный зал. Основная часть храма представляет собой в плане квадрат. Углы кровли, так же, как и у колокольни, украшают кресты на тонких башенках. Необычен световой барабан, он не многогранный или круглый, как обычно, а низкий и квадратный. С каждой стороны в барабане устроены по три полукруглых окна, через которые свет проникает внутрь зала. Храм венчает крест, установленный на большой купол луковичной формы. Реставраторы удачно покрасили внешние стены, сочетание светлого и серого цветов придает церкви необыкновенное очарование. Художники С. Маркин и А. Губский украсили фасад мозаичной иконой святого Феодора Стратилата.

Прямо над центральным входом поднялась трехъярусная колокольня, стройная и легкая, она очень хорошо смотрится на фоне живописной горы Демерджи. В 1995 году специалисты специального научно-производственной фирмы «Крым-авиамонтаж» и крымского государственного предприятия «Заводское» за короткое время, несмотря на холодную погоду, ветер и мокрый снег, вертолетом подняли на 23-метровую колокольню купол, луковицу и позолоченный крест.

Новый храм освятили во имя Всех Крымских Святых и Феодора Стратилата. В день храмового праздника выносят икону «Собор святых и подвижников благочестивых в земле Таврической просиявших», созданную трудами и талантом протоиерея Алексия Медведева и иконописца Виктора Блинова.

В 1992 году в Алуштинском храме возродили древнюю православную традицию: в Крещенскую ночь купаться в море. Известно, что в день Крещения Господня в храмах после Божественной литургии совершается чин великого освящения воды, которая становится особой святыней. Но считается, что в эту ночь все воды наполняются необыкновенной силой, способной помогать при различных недугах. Прихожане храма Всех Крымских Святых начинают готовиться к этому событию задолго до 19 января. Для такого купания они шьют специальные рубашки. В Крещение верующие с зажженными свечами идут к морю, поют молитвы и ровно в 12 часов омываются в волнах. За эти годы многие люди, которые страдали самыми разными заболеваниями, излечились…