Cerkiew wybudowano w 1687 nad Kotoroślą, na terenie słobody Tołczkowo, największej i najzamożniejszej słobody w XVII-wiecznym Jarosławiu. Jej fundatorami, jak również wykonawcami większości prac budowlanych, byli miejscowi rzemieślnicy wytwarzający wyroby skórzane.
Wzorem dla świątyni była cerkiew Wniebowstąpienia Pańskiego w słobodziej Kondakowej. W 1705 do obiektu wstawiono ikonostas wykonany przez Wasilija Komara i Stiepana Woronego, z ikonami jarosławskiego ikonografa Hilariona i kostromskiego mistrza Gurija Nikitina. Freski we wnętrzu świątyni wykonali Fiodor Fiedorow i Fiodor Ignatjew. Dekoracja malarska ukazuje chwałę Matki Bożej i cuda, do których doszło za pośrednictwem ikony, w tym sceny zwycięstw wojennych.Freski ukazują m.in. objawienie się ikony na sośnie, zwycięstwo nad Batu chanem, pożar Kostromy podczas walk z Mongołami, ocalenie Moskwy przed Tamerlanem, oblężenie monasteru Kijowsko-Pieczerskiego przez Litwinów, wyzwolenie Konstantynopola. Malowidła charakteryzuje znaczna dbałość o szczegóły. W 1736 budynek rozbudowano o obszerny przedsionek i galerię. Jeszcze później dostawiono drugi ołtarz, położony od strony południowej.
Cerkiew Fiodorowskiej Ikony Matki Bożej była jedyną świątynią w Jarosławiu, która w okresie ZSRR nie była zamykana i stale pozostawała czynna. Dzięki temu przetrwała także część jego wyposażenia, w tym ikona Chrystusa Pantokratora z ikonostasu. Po zniszczeniu soboru Zaśnięcia Matki Bożej w Jarosławiu świątynia stała się soborem katedralnym eparchii jarosławskiej i rostowskiej.
Szczególną cechą architektury cerkwi są proporcje między jej kopułami a główną bryłą budynku. Podczas gdy wysokość samej nawy wynosi czternaście metrów, usytuowana na niej na bębnie cebulasta kopuła wznosi się na wysokość 22 metrów (bez krzyża), znacznych rozmiarów są również pozostałe cztery kopuły. Bębny, na których umieszczono kopuły, są bogato zdobione fryzami i rzędami kolumienek i arkadek, wykuto w nich ponadto wąskie okna.
W latach 1952–1956 w cerkwi służył hieromnich Nikodem (Rotow), późniejszy metropolita leningradzki. W sąsiedztwie budynku znajdują się groby biskupów jarosławskich Jana i Micheasza.
Autorstwo Fiodorowskiej Ikony Matki Bożej przypisywane jest świętemu Łukaszowi Ewangeliście. Jest to jedna z najważniejszych ikon prawosławia. Przechowywana jest w Monasterze Ipatjewskim w Kostromie.
Ikona przedstawia Matkę Boską z Dzieciątkiem. Wizerunek nawiązuje do innej ważnej ikony, Matki Boskiej Włodzimierskiej i prawdopodobnie jest na niej wzorowany. Jedną swoją nazwę zawdzięcza mieście Kostroma, a drugą – pierwszemu jej posiadaczowi, księciu Jarosławowi Wsiewołodowiczowi, który na chrzcie przyjął imię Fiodor.
Pierwsze wzmianki o ikonie dotyczą darowania jej przez księcia Jarosława jego bratu, Jurijowi Wsiewołodowiczowi, przez którego była przechowywana w kaplicy nieopodal miasta Gorodca. Po jego śmierci, Jarosław odzyskał ikonę i wkrótce przekazał ją swojemu synowi, Aleksandrowi Newskiemu. Ikona trafiła wkrótce do jego brata Wasilija, który umarł w Kostromie.
Z ikoną tą wiąże się podanie, dotyczące okoliczności wstąpienia na tron Michała Romanowa. Sobór Ziemski zapragnął zakończyć wielką smutę, wybierając zaocznie 3 marca 1613 na tron carski Michała Fiodorowicza Romanowa, syna arcybiskupa Rostowa (późniejszego patriarchy moskiewskiego) Filareta, mieszkającego z matką w Kostromie, dokąd też zaraz się udano. Tymczasem młodzieniec niespodziewanie odmówił przyjęcia tronu, tłumacząc się obawą o życie w trudnych czasach smuty; nie zgodziła się na to również jego matka. Wówczas duchowni zaczęli utrzymywać, że ikona przemówiła do nich, wzywając Michała Fiodorowicza do objęcia tronu. Pobożny bojar nie mógł uchylić się od takiego argumentu i tron przyjął. Przed przeprowadzką do Moskwy, matka Michała zażądała jedynie o sporządzenie spisu z ikony, co też się stało. Spis został wykonany i zabrany przez nią ze sobą i umieszczony w cerkwi Narodzenia Matki Bożej. Każdy kolejny car rosyjski był błogosławiony tym wizerunkiem w trakcie uroczystości koronacyjnych.
Według innego podania, tuż przed rewolucją lutową oryginalna ikona zaczerniła się tak, że stała się nieczytelna, co rozumiano jako omen zbliżającego się nieszczęścia.
