Inicjatorami budowy soboru byli gubernator estoński Siergiej Szachowskoj oraz proboszcz parafii Przemienienia Pańskiego w Tallinnie ks. Konstantin Tizik[1]. Wskazywali oni, że istniejący w mieście sobór Przemienienia Pańskiego, przebudowany w XVIII w. z kościoła luterańskiego[2], stał się niewystarczający dla potrzeb rosnącej grupy prawosławnych Rosjan stale zamieszkujących miasto[1]. Zwracali również uwagę na odbiegający bardzo od rosyjskiej prawosławnej tradycji wygląd zewnętrzny tego budynku sakralnego mimo przebudowy[2][a]. Inicjatywa wpisywała się w kampanię wzmacniania prawosławia w guberniach bałtyckich, co z kolei miało sprzyjać rusyfikacji Łotyszy i Estończyków. Wzniesienie soboru, obok otwarcia żeńskiego Piuchtickiego Monasteru Zaśnięcia Matki Bożej, było najpoważniejszą rosyjską inicjatywą w tej kampanii[3].

W 1887 r. Świątobliwy Synod Rządzący zatwierdził plan budowy nowego soboru w mieście i przekazał na ten cel 60 tys. rubli[1]. Gubernator estoński, który pragnął wznieść wspaniałą i efektowną cerkiew, uznał jednak tę sumę za niewystarczającą dla realizacji swoich planów i za zgodą cara Aleksandra III rozpoczął ogólnorosyjską zbiórkę funduszy na budowę obiektu. W rezultacie do połowy września 1899 r. zebrano 434 623 ruble i 29 kopiejek[4]. Siergiej Szachowskoj nie dożył jednak nawet rozpoczęcia budowy soboru[5].

Na patrona świątyni wybrano w 1888 r. św. Aleksandra Newskiego, aby uczcić ocalenie cara Aleksandra III i jego rodziny z katastrofy monarszego pociągu w Borkach 17 października tego roku[6]. Jako miejsce pod budowę świątyni wybrane zostało kluczowe w rozplanowaniu Tallinna i istotne dla estońskiej mitologii narodowej wzgórze Toompea[1][b], a konkretnie plac przed pałacem gubernatorskim (pierwotnie zamkiem Toompea, w niepodległej Estonii jest to gmach parlamentu)[6]. Autorem projektu budynku był akademik Michaił Prieobrażenski[1]. 30 sierpnia 1893 r. arcybiskup ryski i mitawski Arseniusz poświęcił miejsce budowy, dwa lata później rozpoczęto wylewanie fundamentów[1]. 20 sierpnia 1895 r. poświęcony został kamień węgielny[7]. 2 listopada 1897 r. z fundacji kupca Iwana Gordiejewa na kopułach nieukończonej jeszcze cerkwi ustawiono żelazne, złocone krzyże[7]. Rok później, latem, z daru przekazanego przez kolejnego rosyjskiego kupca Piotra Abrosimowa sfinansowano pozłocenie pięciu kopuł soboru. Dzwony dla świątyni odlano w zakładzie Wasilija Orłowa w Petersburgu[7], a zawieszono je w soborze 7 czerwca 1898 r.[8].

Początkowo budowniczowie soboru przewidywali wstawienie do niego marmurowego ikonostasu, ostatecznie jednak zdecydowano się na drewniany i złocony[9] jako tańszy, a przy tym bardziej pasujący stylistycznie do całości. Wygląd ikonostasu również zaprojektował Michaił Prieobrażenski, zaś wykonał go S. Abrosimow[10]. Ikonostas został umieszczony we wnętrzu soboru w 1899 r., a ikony do niego powstały w pracowni Aleksandra Nowoskolcewa[1]. Akademik Nowoskolcew osobiście napisał wizerunki w dolnym rzędzie ikonostasu[11].

W marcu 1900 r. ukończono prace nad wystrojem wnętrza i 30 kwietnia tegoż roku biskup ryski i mitawski Agatangel, w asyście protoprezbitera Jana Siergiejewa poświęcił gotową świątynię[1]. 2 maja tego samego roku biskup Agatangel konsekrował boczny ołtarz św. Sergiusza z Radoneża, natomiast 15 lipca miało miejsce wyświęcenie ołtarza św. Włodzimierza[12]. Sobór był świątynią parafii etnicznie rosyjskiej (z nabożeństwami w języku cerkiewnosłowiańskim), starszy sobór Przemienienia Pańskiego przekazano parafii prawosławnych Estończyków[1].

W 1917 r. metropolita piotrogrodzki Beniamin w asyście biskupa łuskiego Artemiusza dokonał w soborze św. Aleksandra Newskiego pierwszej w historii chirotonii biskupiej duchownego narodowości estońskiej – Platona (Kulbuscha)[13]. Biskupi żezł wręczony Platonowi (zamordowanemu w 1919 r. i kanonizowanemu jako jeden z nowomęczenników rosyjskich), traktowany jak relikwia, jest przechowywany w soborze[13].

W dwudziestoleciu międzywojennym w soborze odbywały się chirotonie biskupie kolejnych estońskich hierarchów prawosławnych – Aleksandra (Paulusa), Jana (Bulina) oraz Mikołaja (Leismana)[14].

Po uzyskaniu niepodległości przez Estonię pojawił się projekt adaptacji soboru i całego wzgórza Toompea na Panteon Estońskiej Niezależności, a tym samym usunięcia świątyni-symbolu rusyfikacji kraju[1]. W październiku 1928 r. estoński parlament uchwalił ustawę o rozbiórce soboru, która miała dojść do skutku do 1 maja 1929 r.[15]. Decyzja ta spotkała się z protestami ludności prawosławnej, a także części duchowieństwa i wiernych większościowego w Estonii Kościoła luterańskiego oraz lewicowych partii opozycyjnych. Ostatecznie do zniszczenia świątyni nie doszło[1]. Jedynie z kopuł soboru zdjęto złoto[15].

W latach 1923–1936 soborem administrowała nadal parafia rosyjska, podlegająca eparchii narewskiej, grupującej placówki duszpasterskie przeznaczone dla prawosławnych Rosjan. W 1936 r. budynek przejęła parafia etnicznie estońska; równocześnie sobór stał się katedrą autonomicznego Estońskiego Kościoła Prawosławnego kierowanego przez metropolitę Aleksandra. Nabożeństwa odbywały się w języku estońskim[1]. Parafii rosyjskiej przekazano w zamian znacznie mniejszą cerkiew Świętych Symeona i Anny w Tallinnie[15].

Parafia rosyjska ponownie zaczęła funkcjonować w soborze w 1940 r., po aneksji Estonii przez ZSRR i ponownym włączeniu Estońskiego Kościoła Prawosławnego w jurysdykcję Patriarchatu Moskiewskiego[1].

Po zajęciu Estonii przez III Rzeszę wskutek agresji na ZSRR sobór został w 1941 r. zamknięty[1]. Niemieckie władze okupacyjne rozważały jego całkowite zniszczenie[16]. Do ponownego otwarcia cerkwi w marcu 1945 r. doprowadził arcybiskup narewski Paweł. W 1947 r. wiernym odebrano piwnice świątyni, gdzie znajdowała się dolna cerkiew św. Andrzeja, po czym zaadaptowano je na schron, a następnie magazyn książek. W latach 60. XX wieku istniał projekt przebudowy całego soboru na planetarium, czemu skutecznie przeciwstawił się biskup talliński i estoński Aleksy[1].

W 1990 r. w soborze odbyła się chirotonia biskupia archimandryty Korneliusza (Jakobsa), który objął następnie urząd biskupa tallińskiego[17].

W 1991 r. parafia soborowa odzyskała pomieszczenie po dolnej cerkwi. Osiem lat później obiekt, na wniosek parafian, otrzymał status soboru stauropigialnego – podlega bezpośrednio patriarchom moskiewskim i całej Rusi, nie zaś eparchii tallińskiej, chociaż pozostaje katedrą jej zwierzchników[1].

Sobór dwukrotnie odwiedzali patriarchowie moskiewscy i całej Rusi – Aleksy II w 2003 r.[18] i Cyryl w 2013 r.[19]. 29 maja 2018 r. w świątyni odbył się nadzwyczajny sobór duchowieństwa i świeckich Estońskiego Kościoła Prawosławnego, który dokonał wyboru nowego zwierzchnika Kościoła po śmierci metropolity Korneliusza w marcu tego samego roku[20].

20 września 1995 sobór został zarejestrowany na liście zabytków kultury Estonii (est. Kultuurimälestiste riiklik register) pod numerem 1102[21].