Podobnie jak wiele innych parafii prawosławnych na Ziemiach Zachodnich także i parafia w Koszalinie powstała niedługo po zakończeniu wojny w trakcie organizowania nowej Diecezji Wrocławsko — Szczecińskiej. Jest jedną z kilkunastu które należały do dekanatu koszalińskiego powołanego przez Sobór Biskupów z dniem 1 sierpnia 1958 roku.
Należały do nich następujące parafie:
1. Bobolice
2. Bytów
3. Drzonowo
4. Karścino
5. Konikowo
6. KOSZALIN
7. Ołóżna
8. Rokosowo
9. Rzeczenica
10. Sławno
11. Słupsk
12. Szczecinek — Bobolice
13. Wałcz
Decyzją Wydziału do Spraw Wyznań w Warszawie w dniu 20 sierpnia 1953 roku na wniosek Prezydium Wojewódzkiej Rady Narodowej w Koszalinie z dnia 31 lipca 1953 roku oddano w użytkowanie Polskiemu Autokefalicznemu Kościołowi Prawosławnemu działkę wraz z zabudowaniami przy ulicy Mickiewicza i ulicy Asnyka w Koszalinie. Był to były kościół ewangelicki wraz z budynkiem mieszkalnym.
Faktycznie jednak początki parafii należy odnieść do 1 sierpnia 1954 roku. Wtedy to na parafię zostaje delegowany ksiądz Dymitr Doroszkiewicz. Był to pierwszy proboszcz parafii, późniejszy dziekan, który od samego początku z wielką gorliwością i poświęceniem organizował życie w nowopowstałej parafii. W tym okresie parafia była bardzo zróżnicowana pod względem narodowościowym — w jej skład wchodzili Białorusini, Łemkowie, Ormianie, Ukraińcy, Rosjanie. Na początku było około 50 rodzin.
Budynek odziedziczony po kościele ewangelickim wymagał wielu prac remontowych. W roku 1959, dzięki działalności księdza Dymitra, wnętrze budynku uzyskało wygląd świątyni nawiązującej do tradycji wschodniej ( ikonostas, boczne ściany). Trzy lata później ksiądz Doroszkiewicz został dziekanem okręgu koszalińskiego i niedługo potem także proboszczem parafii w Słupsku.
Nowe obowiązki księdza Doroszkiewicza, w tym obsługiwał także kilka innych parafii w dekanacie, spowodowały, że nabożeństwa w cerkwi koszalińskiej przestały być odprawiane systematycznie. Sytuacja miała się zmienić kiedy na parafię delegowano księdza Mikołaja Turowskiego — drugi proboszcz. Jednakże jego stan zdrowia i wiek nie pozwoliły na czynne wypełnianie swoich obowiązków. Także kolejnemu proboszczowi księdzu Mikołajowi Leszczyńskiemu (bardzo długo chorował i wkrótce zmarł) nie udało się przywrócić regularnych nabożeństw. W tym okresie, jak wspomina w listach ksiądz Doroszkiewicz, parafia znacznie się zmniejszyła.
W 1965 roku parafię objął nowy proboszcz – o. Aleksander Jaroszuk. Z jego przyjściem rozpoczęły się regularne nabożeństwa, Św. Liturgie i wieczorne — wsienoszcznyje. Wierni mocno cenili duszpasterską działalność o. Aleksandra i czynnie uczestniczyli w życiu swojego kościoła. Trudne momenty jakimi były akty wandalizmu (wybijanie szyb i inne) udawało się przezwyciężać. Dzięki czemu parafia żyła w silnej więzi chrześcijańskiej. Dwukrotnie posługę duszpasterską w latach 1964 oraz w 1966 pełnił ksiądz Sergiusz Kosacki. Ciężka choroba, na którą zapadł młody proboszcz doprowadziła do śmierci w styczniu 1967 roku.
Kolejnym proboszczem zostaje w Koszalinie ksiądz Jakub Solar, który sprawował swe obowiązki do roku 1970. Po nim obowiązki proboszcza przejął ksiądz Włodzimierz Sawczuk. W tym okresie jak wspominają obecnie — żyjący parafianie — cerkwi przybyło wielu wiernych. Msze odprawiano w języku słowiańskim i ukraińskim, co często powodowało pewne nieporozumienia, które zakłócały modlitewny nastrój. Ksiądz Sawczuk swoją funkcję sprawował dwa lata, a następnie oddelegowany został do parafii na białostocczyźnie w Tyniewiczach Dużych. Nowym administratorem został ksiądz Jerzy Doroszkiewicz, który służył w Koszalinie do 1974 roku. Powołany został później na Kanclerza w Kancelarii Metropolitarnej.
Następnym proboszczem był ksiądz Michał Szlaga. Nowy proboszcz dobrze znał realia parafii koszalińskiej, gdyż poprzednio pełnił służbę w Szczecinku. Energicznie przystąpił do działalności duszpasterskie. Dzięki niemu odbył się kapitalny remont cerkwi, która wymagała wielu prac remontowych. W krótkim czasie wyremontowany został dach i wieża cerkwi, odnowiono wnętrze oraz wykonano elewację zewnętrzną. Dzięki ofiarnej pomocy wiernych i trafnym poczynaniom księdza Szlagi szybko zakończono prace i zabezpieczono trzynastowieczny budynek przed zniszczeniem. Praca wiernych i proboszcza została doceniona przez Biskupa Ordynariusza. Podczas poświęcenia cerkwi, w roku 1978 , nagrodził wszystkich, którzy przyczynili się do odnowienia kościoła.
W roku 1981 do Koszalina zostaje skierowany dekretem Biskupa Aleksego ksiądz mitrat Jan Krzemiński. Sprawuje on obowiązki proboszcza i dziekana do końca roku 1987. Jeszcze za probostwa księdza Krzemińskiego ( z powodu choroby często nie mógł odprawiać nabożeństw) do pomocy zostaje delegowany z Wrocławia jako wikariusz — ksiądz Mikołaj Lewczuk. W grudniu 1987 roku przejmuje on obowiązki proboszcza, a 28 grudnia otrzymuje także funkcję dziekana okręgu koszalińskiego. W 1988 roku staraniem kurii i nowego proboszcza parafia prawosławna otrzymała nowe mieszkanie. W mieszkaniu tym mógł zamieszkać proboszcz, który wcześniej dojeżdżał do Koszalina z Wrocławia. Ksiądz Mikołaj Lewczuk do dzisiaj sprawuję obowiązki proboszcza w parafii koszalińskiej.
Nabożeństwa odbywają się w niedzielę o godzinie 10, w każde większe święto, a także w soboty o 17 odprawiane są wieczorne nabożeństwa. Językiem liturgii jest starocerkiewno-słowiański, z tym że komunikaty podawane są także w języku polskim. Literatura i katecheza jest dostępna w językach narodowych, a także w języku polskim. Prasę kościelną stanowią dwa czasopisma o zasięgu krajowym — «Wiadomości Polskiego Autokefalicznego Kościoła Prawosławnego» i «Przegląd Prawosławny» oraz inne w językach narodowych.
Według księdza Mikołaja obecnie w kościele jest około 100 praktykujących rodzin. Nie są w to wliczane osoby, które sporadycznie przychodzą na msze — głównie te związane z wielkimi świętami (Wielkanoc, Boże Narodzenie). Parafia nie posiada dokładnych danych co do liczby wiernych wyznania prawosławnego. Jednak szacuję się, że jest ich dużo więcej szczególnie z Ukrainy, Białorusi, Gruzji.. Parafia koszalińska jest wielonarodowościowa. Należą do niej Białorusini, Gruzini, Łemkowie ,Ormianie Polacy, Rosjanie, , Ukraińcy
Zajęcia z religii odbywają się w szkole oraz na plebani — młodzież starsza, skupiona w Bractwie Młodzieży Prawosławnej. W tym roku odbył się kolejny Zjazd Młodzieży Prawosławnej, który miał miejsce na Św. Górze Grabarce. Takie zjazdy odbywały się także w Cieplicach i w Jeleniej Górze. Rok temu, nie tylko dla młodzieży ale i pozostałych wiernych, parafia zorganizowała pielgrzymkę do Grecji, gdzie poznawano również liturgię.
Parafia prawosławna p.w. Zaśnięcia Przenajświętszej Bogurodzicy w Koszalinie należy do dekanatu koszalińskiego, w skład którego wchodzi obecnie 5 parafii, a więc Koszalin, Wałcz, Słupsk, Szczecinek i Bobolice. Dekanat koszaliński jako jeden z 6 należy do Diecezji Wrocławsko — Szczecińskiej. Kontakty ekumeniczne utrzymywane są ze wszystkimi parafiami rzymskokatolickimi, jak i innych kościołów. Od 30 lat trwa bliska współpraca z parafiami rzymskokatolicką i ewangelicko-augsburską w Nussloch (Niemcy).
Cerkiew mieści się w XIII-wiecznym, poewangelickim kościele, który nie przypomina typowej świątyni prawosławnej. Ceglany, jednoprzestrzenny kościół wzniesiony został na planie prostokąta. Od strony zachodniej znajduje się dobudowana później kruchta. Całość przykrywa dwuspadowy dach z ośmioboczną wieżą i sygnaturką. Nawę oświetlają wysokie, smukłe, ostrołukowe okna. Wschodnia elewacja kościoła zachowała gotycki łuk tęczowy oraz dekoracyjny parapet ceglanego lektorium.
Świątynia powstała prawdopodobnie już około 1300 roku jako kościół klasztorny cysterek. Od czasu reformacji, po opuszczeniu klasztoru przez mniszki kościół popadł w ruinę. Odbudowany został dopiero w latach 1602 — 1609 za panowania księcia Franciszka i odtąd pełnił funkcje kościoła zamkowego. W czasie pożaru miasta w 1718 roku budowla spłonęła niemal doszczętnie. Ocalałe z pożogi mury wykorzystano podczas odbudowy. Gruntowny remont przeprowadzono dopiero w latach 1818 — 1819. Kościół ponownie poświęcono w 1820 roku. Od tego czasu czyniono wiele starań o zachowanie dobrego stanu technicznego i upiększenie świątyni. W 1839 roku wzniesiono wieżę z sygnaturą, a w 1865 dobudowano przedsionek od strony zachodniej, mieszczący kruchtę. Ostatni przedwojenny remont został dokonany w 1928 roku i wówczas odkryto gotyckie elementy, przy czym część z nich otynkowano, a odsłonięto jedynie ścianę wschodnią. Po drugiej wojnie światowej kościół przekazano Polskiemu Autokefalicznemu Kościołowi Prawosławnemu.
Od 1954 roku cerkiew była w miarę potrzeb i możliwości remontowana, o czym już wcześniej wspomniano. Od 1987 proboszczem jest ks. Mikołaj, do dnia dzisiejszego tj 2021r.
Od roku 1990 wykonano szereg niezbędnych prac w celu należytego utrzymania stanu technicznego jak i samej funkcjonalności i estetyki obiektu. Na początku lat dziewięćdziesiątych przeprowadzona remont dachu (wymiana dachówki) jak i wieży, którą za zgodą Wojewódzkiego Konserwatora Zabytków pokryto blachą miedzianą a na jej szczycie umieszczono sześcioramienny prawosławny krzyż. Pod jubileusz 40-lecia wykonano sposobem gospodarczym remont wnętrza cerkwi. W latach 1995-1997 dzięki pomocy Fundacji Współpracy Polsko-Niemieckiej udało się dokonać wymiany elewacji zewnętrznej, osuszenia fundamentów i murów obiektu (metodą iniekcji krystalicznej) i założenia izolacji poziomej i pionowej, co już dzisiaj po 10 latach okazało się trafnym i pozytywnym dokonaniem. Wykonano ze strony południowej fosę, założono instalację wodno-kanalizacyjną i instalację odprowadzającą wodę z połaci dachu do miejskiej kanalizacji. To też wpłynęło na stan murów i ich osuszenie. Kilka lat starań zaowocowało pozyskaniem terenu wokół cerkwi a następnie jego ogrodzeniem płotem metalowym zamocowanym w słupach z cegły klinkierowej zakończone na początku 2001 roku. Dwa lata później w 2003 r. założona została instalacja alarmowa. Przed jubileuszem 50-lecia parafii w 2004 r. odrestaurowano wnętrze cerkwi, stolarkę i ściany. W roku 2005 korzystając z pomocy Fundacji Renovabis, Urzędu Miejskiego w Koszalinie i własnym środkom zainstalowano ogrzewanie elektryczne w cerkwi.
W rok 2014 wykonano generalny remont połaci dachowej jak i stropu dachu cerkwi koszta ponad 600 tyś. — Ministerstwa Kultury , Urzędu Miasta Koszalina i własne.W roku 2017 parafia zakupiła od miasta kamiennicę przy. ul. Mickiewicza 9 w Koszalina naprzeciwko cerkwi z przeznaczeniem na Dom Opieki i Spotkań Ekumenicznych w tym kancelaria parafii, biblioteka i mieszkanie dla duchownych i wiernych. Na chwilę obecną wyremontowano dach budynku, parter i częściowo 1 piętro.
Cerkiew sukcesywnie wymaga opieki i nadzoru, stąd nowa Rada Parafialna wraz z Proboszczem nieustannie poszukuje rozwiązań aby ten zabytkowy obiekt położony w centrum miasta wyglądał należycie i służył wizytówką tej części Starego Miasta. Najbliższe zamierzenia to NAPRAWA WIEŻY CERKWI I KRZYŻA zniszczone przez wichurę w marcu 2019 roku.
Życie parafii to przede wszystkich sprawy religijne-duchowe, liturgiczne na które zwraca szczególnie ksiądz proboszcz., a świątynia, jej stan, wygląd znacznie pomaga w realizowaniu posługi chrześcijańskiej.
W 2021 został zakończony remont sygnaturki kościoła prawosławnego. Wykonywana jest wykonana wykonana wykonana magia wieży, odgromienia i balustrady na wieży nowego nowego roku. Poprzednie zniszczony 03.12.2020 podczas wichury. Więcej zdjęć z remontu w galerii