Граф М. С. Воронцов (1782-1856), який дбає про благоустрій Південного берега Криму, вирішив побудувати в Алушті великий храм. Підготувати проект майбутньої церкви він доручив архітектору Торічеллі (1796-1843). Вона була освячена 30 листопада 1842 протоієреєм ялтинської церкви Сорокіним з благочинним священиком Накропіним на честь Феодора Стратилата. Першим священиком став о. Михайло Родіонов.
Храм збудували на кошти держави, іконостас з липового дерева виготовили на кошти міщанина з Чернігівської губернії Бочарова.
Храм був побудований в готичному стилі і нагадував сільські церкви в Англії. Керівництво 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 годині омиваються у хвилях. За ці роки багато людей, які страждали різними захворюваннями, вилікувалися.