До кінця ХIХ століття місто зросло і ялтинці вирішили звести великий собор.
Історія будівництва собору пов’язана з російським імператорським домом. Собор Олександра Невського було побудовано в пам’ять російського імператора Олександра II, який загинув 1 березня 1881 року від бомби, що розірвалася біля його ніг.
1 березня 1890 року заснували будівельний комітет, який очолив відомий інженер, учений, краєзнавець А.Л.Бертьє-Делагард. До складу комітету увійшли тридцять шанованих ялтинців. Велику ділянку землі, розташовану з місцем будівництва, пожертвував барон А.Л.Врангель.
Перший проект храму розробив 1889 року архітектор К.І.Ешліман, але він не був затверджений. Новий проект доручили зробити М.П.Краснову, який працював у співавторстві з П.К.Теребенєвим. 1 березня 1891 року в день десятої річниці з дня загибелі імператора Олександра II відбулася урочиста закладка фундаменту нового храму.
Архієпископ Мартиніан відслужив молебень просто на будівельному майданчику. Перший камінь майбутнього храму поклала імператриця Марія Федорівна.
Для храму архітектор вибрав давньоруський стиль, застосувавши безліч декоративних архітектурних елементів: пілястрів, порталів, кіотців, сердечок. Собор побудували двоярусним, з відкритими галереями і шатровим ґанком. Пофарбували його в біло-рожеві тони, що зробило його ошатним, святковим. Ікони для храму виготовили в Мстері Володимирської губернії.
11 дзвонів для триярусної дзвіниці собору відливали в Москві, головний дзвін важив 428 пудів. Усі дзвони храму подарував кримський винопромисловець і меценат Н.Д.Стахеєв.
Освячення собору відбулося 4 грудня 1902 року архієпископом Миколою. На урочистій службі була присутня імператорська сім’я, яка прибула з Лівадії.
Пишність і незвичайна краса зовнішнього вигляду храму повинна була поєднуватися і з внутрішнім оформленням. Тому 1901 року провели всеросійський конкурс, переможець якого зміг би оформити інтер’єр Олександро-Невського собору. Перше місце посів архітектор С.П.Крошечник. За проектами Краснова київський художник І.Мурашко розписав іконостас, ним же виконано суцільний розпис купола і стін у візантійському стилі. На зовнішній стороні храму, в гранітній рамі-кіоті розташували мозаїчне панно з образом святого князя Олександра Невського. Мозаїка була виконана учнями венеціанського майстра Антоніо Сальвіаті.
Храм двопрестольний: верхній престол освячений в ім’я святого Олександра Невського, а нижній — в ім’я святого Артемія, цього святого церква вшановує 20 жовтня, цього дня помер імператор Олександр III. Усі куполи собору вкрили золотом.
В єдиному стилі з храмом пізніше був побудований двоповерховий будинок притча, що нагадував давньоруський терем. Його автором став М.І.Котенков. У 1903-08 роках побудували ще один будинок у три поверхи, тут знаходився великий актовий зал для Олександро-Невського братства.
У цьому будинку розмістилася церковно-парафіяльна школа та притулок для слабогрудих хворих. Школу назвали ім’ям цесаревича Олексія.
Православне братство святого благовірного князя Олександра Невського було створено за указом імператора Олександра III і Таврійської Духовної консисторії при сімферопольському кафедральному соборі 23 листопада 1868 року. Засновником братства став архієпископ Гурій (Карпов). Завдання братства були різноманітні: створювати церковно-парафіяльні школи, надавати їм і храмам матеріальну допомогу, зводити нові церкви, піклуватися про бідних, людей похилого віку та сиріт, боротися з розколами і сектантством. Під час Першої світової війни Олександро-Невське братство і громада сестер милосердя Червоного хреста збирала подарунки, ліки, лікарські трави для солдатів, влаштовували лазарети і санаторії для поранених.
Першим протоієреєм собору став Олександр Якович Терновський, який раніше служив у храмі Іоанна Златоуста.
Храм розділив із парафіянами тяготи революції та громадянської війни, тут на тільки підтримували віру в людях, собор охороняв, оберігав життя людей. У 1918 році під час обстрілу Ялти червоногвардійцями в його стінах ховалися жителі міста.
У червні 1918 року в нижньому храмі відспівували дружину Ф.М. Достоєвського Анну Григорівну. Її поховали на цвинтарі в Алупці, і лише через багато років її прах перенесли в Олександро-Невську лавру в Петербурзі, де поховано Ф.М.Достоєвського.
У 1938 році собор закрили. Дзвони зняли і відправили на переплавку. У храмі організувався спортивний клуб.
Богослужіння в соборі було відновлено 1945 року і відтоді не припинялося. Храму повернули будівлю церковно-парафіяльної школи, де раніше був будинок учителя.