Główny inicjator powstania cerkwi, Fiodor Michajłow nie doczekał ukończenia jej budowy, umierając jeszcze pod koniec 1886.
Kamień węgielny pod budowę cerkwi został wmurowany 8 czerwca 1886Daty z okresu Imperium Rosyjskiego podane w starym stylu. z błogosławieństwem biskupa jekaterynburskiego Nataniela. Budynek w stanie surowym został ukończony już w 1887, a następne trzy lata zająć miały prace wykończeniowe, kompletowanie wyposażenia, sprzętów liturgicznych oraz tworzenie dekoracji. 17 czerwca 1890 budowa była już ukończona, wtedy też biskup jekaterynburski Polikarp konsekrował cerkiew Wszystkich Świętych. Świątynia według ówczesnych jednostek długości liczyła od wschodniej strony ołtarza do zewnętrznej zachodniej ściany 13 sążni, a jej szerokość wynosiła 5 sążni. Ikonostas był dwurzędowy, kolorem dominującym była czerwień. Głównymi problemami jakie trapiły ten nowy jekaterynburski obiekt sakralny w latach 1890–1904 były przede wszystkim: chroniczny brak kapłanów, a także niska frekwencja na nabożeństwach. Sama świątynia nie była samodzielną parafią, lecz podlegała pod sobór św. Katarzyny. Jednocześnie cały czas trwały prace wewnątrz budynku. W 1900 otynkowano kopułę, oczyszczono zewnętrzne ściany i pomalowano dach, a wewnątrz odnowiono ściany i posadzkę.