Рост православного населения в Таллинне в конце XIX века потребовал строительства нового Православного собора. Выполнявшая роль кафедрального собора Преображенская церковь, перестроенная из средневековой монастырской, тесная и неудобно расположенная, не удовлетворяла возросшим требованиям к главному храму Эстляндии. Князь Сергей Владимирович Шаховской, в 1885 году назначенный Эстляндским губернатором, стал инициатором строительства нового собора и исходатайствовал Высочайшее разрешение на сбор в пределах империи средств для осуществления названной цели. Со всей России поступали пожертвования на постройку в Рсвеле нового соборного храма. В итоге на 15 сентября 1899 года было собрано 434 623 рубля 29 коп.

В честь чудесного спасения царя Александра III и его семьи при страшном крушении императорского поезда 17 октября 1888 года было решено посвятить новый собор Святому Благоверному Князю Александру Невскому. Выбору места для строительства уделялось едва ли не первостепенное значение. Из восьми предложенных вариантов наиболее подходящей оказалась площадь перед губернаторским дворцом на Вышгороде. 30 августа 1893 года состоялось торжественное освящение места для будущего храма, на церемонию из Пюхтицкого монастыря была доставлена чудотворная икона Успения Божией Матери.

Проект собора был заказан у специалиста по церковным постройкам академика архитектуры Михаила Тимофеевича Преображенского, члена Санкт-Петербургской Академии художеств. 20 августа 1895 года состоялась торжественная церемония освящения закладки храма. А двумя годами позже, 2 ноября 1897 года, благодаря стараниям главного подрядчика купца 1-ой гильдии Ивана Дмитриевича Гордеева, на соборе торжественно установлены железные позолоченные кресты. Позолота глав собора произведена в течение лета 1898 года позолотных дел мастером купцом 2-ой гильдии Петром Семеновичем Абросимовым. Колокола для собора были изготовлены на колокольном заводе купца Василия Михайловича Орлова в Санкт-Петербурге. Весь звон составляет 11 колоколов. Торжество освящения и поднятия колоколов состоялось 7 июня 1898 года. Первоначально проект собора предусматривал установку мраморного иконостаса, но в ходе строительства было решено заменить его золоченым деревянным. Работа была поручена П. С. Абросимову. Иконы были написаны в мастерской академика живописи Александра Никаноровича Новоскольцева. По его же эскизам петербургским мастером Эмилем Карловичем Штейнке сделаны витражи, установленные в алтарных окнах главного придела. Пятиглавый трехпрестольный храм, вмещающий 1500 человек, выполнен по образцу московских храмов XVII века. Фасады собора украшены мозаичными панно работы академика архитектуры А. Н. Фролова.

Торжественное освящение собора во имя Святого Благоверного Князя Александра Невского было совершено 30 апреля 1900 года Преосвященным Агафангелом, епископом Рижским и Митавским. В освящении участвовал св. прав. о. Иоанн Кронштадтский.

В начале 20-х годов в Эстонии был начат сбор средств на снос собора - "памятника русского насилия". В конце 1928 года в Государственное Собрание был внесен законопроект о сносе Александро-Невского собора. С помощью мировой православной общественности храм удалось отстоять. В период фашистской оккупации собор был закрыт, а на повестку дня вновь стал вопрос о его сносе.

В начале 60-х годов от перестройки под планетарий храм спас молодой епископ Таллинский и Эстонский Алексий (Ридигер), Святейший Патриарх Московский и Всея Руси Алексий II.

В 1999 году в знак особого покровительства Таллиннскому Кафедральному собору св. Александра Невского был дан статус ставропигиального, т.е. храма, напрямую подчиненного Патриарху Московскому и Всея Руси.

Проект собора был заказан адъютант-профессору Академии Художеств академику Михаилу Тимофеевичу Преображенскому. Это был проект пятиглавого трёх-престольного соборного храма на 1500 человек в стиле древних русских церквей, с одной ризницей, доступной для всех алтарей, с подвалом под храмом для камеры парового отопления, склада дров, крестильни, комнаты сторожа, светлого помещения для церковного архива с библиотекой и, наконец, с папертью при главном западном входе.

В качестве главного подрядчика был приглашён санкт-петербургский первой гильдии купец Иван Дмитриевич Гордеев, строивший в это время в Таллине здание Окружного суда. Летом 1895 года были закончены фундамент, подвальный этаж и подливка цоколя и начата кладка стен и пилонов, которые сооружались из местной известняковой плиты на цементном растворе и отделывались снаружи зегерсдорфским кирпичом. Цоколь облицовывался финским гранитом. Кровля собора покрыта оцинкованным железом, и сделаны купола, которые покрыты простым железом чешуйчатыми квадратными листами. На куполах водружены железные позолоченные кресты.

20 августа 1895 года архиепископ Арсений совершил торжественное освящение закладки собора.
Во время общего большого ремонта храма, начатого в 1990 году по инициативе настоятеля собора епископа Виктора (Подольского), решено было отремонтировать и кровлю. Перед организаторами ремонта встал вопрос: повторить покрытие из оцинкованной жести, выполнив работу с меньшими затратами и за один сезон, либо восстановить историческое чешуйчатое покрытие куполов. Решено было вернуть на луковицы первоначальное чешуйчатое покрытие из медной жести.
Тогда же, вместо полностью проржавевших старых крестов, были изготовлены и установлены новые кресты, представлявшие собой точную копию прежних. Кресты сделаны из нержавеющей стали, покрыты медным листом и вызолочены мастером И.Таэль.

Звон собора составляет 11 колоколов. На колоколах отлиты следующие изображения и надписи:
На 1-м колоколе. Образа Спасителя и Александра Невскаго. Надпись: "И ины овцы имам, яже не суть от двора сего и тыя ми подобает привести и глас мой услышать, и будет едино стадо и един пастырь. Иоан. 10, 16".
"Колокол Ревельскаго Александро-Невскаго Собора, начатаго постройкою в 1894 году с соизволения ГОСУДАРЯ ИМПЕРАТОРА АЛЕКСАНДРА III по почину и усердием Эстляндскаго Губернатора Князя Сергия Владимировича Шаховскаго и достроеннаго в царствование ИМПЕРАТОРА НИКОЛАЯ II стараниями Эстляндскаго Губернатора Евстафия Николаевича Скалона и членов председательствуемаго им комитета".
На 2-м колоколе: Образа Благовещения Пресвятыя Богородицы и Николая Чудотворца. Надпись: "Благовествуй земле радость велию, хвалите небеса Божию славу".
"Колокол Ревельскаго Александро-Невскаго Собора, закладка коего совершена Архиепископ. Рижск. и Митавск. Арсением. Колокол отлит при управлении епархиею Епископом Агафангелом".
На 3-м колоколе: Образа Преподобнаго Сергия Радонежскаго и Вознесенья Господня. Надпись: "Кто взыдет на гору Господню или кто станет на месте святем Его? Неповинен рукама и чист сердцем ". Пс. 23, 3 - 4.
"Колокол Ревельскаго Александро-Невскаго Собора."
На 4-м колоколе: Образ Князя Владимира.
На всех остальных колоколах одинаковая надпись: "Колокол Ревельскаго Александро-Невскаго Собора".