Według miejscowej, ustnie przekazywanej legendy, w tym miejscu, gdzie znajduje się kościół pw. św. Mikołaja, w czasach przedchrześcijańskich było uroczysko jako pogańskie miejsce kultu. Od najdawniejszych czasów utrzymywała się też tradycja, że na te ziemie dotarli św. Cyryl i św. Metody, przynosząc światło wiary chrześcijańskiej obrządku wschodniego, bizantyjskiego. I właśnie w tym miejscu nauczali lud wiary w Chrystusa. Po ich odejściu ludność miała wybudować małą, drewnianą cerkiew, która jednak w następnych latach poszła w zapomnienie i z czasem uległa zniszczeniu.
Po wybudowaniu Zamościa osiedlili się tutaj kupcy greccy, którzy byli wyznania chrześcijańskiego, ale obrządku wschodniego podlegającego patriarchatowi konstantynopolitańskiemu, a nie moskiewskiemu. Kiedy w XV w. sytuacja Konstantynopola stawała się coraz bardziej trudna z powodu zagrożenia tureckiego, po intensywnych staraniach Kościół wschodni zawarł Unię z Kościołem rzymskim, zachodnim na Soborze we Florencji w 1439 r.
Kupcy greccy zamieszkali w Zamościu. Zwrócili się do hetmana Jana Zamoyskiego z prośbą o pozwolenie na wybudowanie cerkwi. Jan Zamoyski przychylił się do ich prośby i wyznaczył miejsce, gdzie według legendy stała jej poprzedniczka zbudowana w wyniku misyjnego nauczania przez św. Cyryla i św. Metodego. Wobec tego wydał 10 stycznia 1589 r. przywilej pozwalający prawosławnym Grekom na wzniesienie w mieście cerkwi. Początkowo wybudowano małą, drewnianą świątynię. Następnie syn Jana, Tomasz Zamoyski, pozwolił Grekom wystawić murowaną renesansową cerkiew według projektu Jaroszewicza i Wolffa. Budowa trwała w latach 1618-31 i w tym to roku cerkiew poświęcono, nadając jej tytuł św. Mikołaja. Pieniądze zarówno na budowę cerkwi, jak i jej utrzymanie pochodziły ze składek kupców greckich. Taki stan rzeczy trwał do 1706 r., kiedy Anna z Gnińskich Zamoyska, podskarbina koronna, gorliwa katoliczka, odebrała cerkiew prawosławnym, a sprowadziła tutaj zakonników unickich, bazylianów. Stało się tak, ponieważ zmniejszyła się liczba prawosławnych Greków. Ponadto część prawosławnych przystąpiła do unii brzeskiej w 1596 r., uznając tym samym zwierzchnictwo papieża z zachowaniem jednak liturgii bizantyjskiej, wschodniej.
Oprócz cerkwi pw. św. Mikołaja istniała jeszcze cerkiew na Lwowskim Przedmieściu (dziś Nowe Miasto), która wraz z całą diecezją chełmską przeszła do unii brzeskiej. Wobec tego wydawało się wówczas, że przejście do unii całego prawosławia to tylko kwestia czasu, skoro nawet car Rosji Piotr I (1672-1725) miał deklarować swoje poparcie dla katolików.
W 1720 r. odbył się w zamojskiej cerkwi pw. św. Mikołaja synod Kościoła greckokatolickiego pod przewodnictwem metropolity Leona Kiszki. W następnych latach cerkiew znajdująca się na Przedmieściu Lwowskim popadła w ruinę i dlatego została rozebrana. Wtedy w 1794 r. przeniesiono parafię unicką do cerkwi pw. św. Mikołaja, którą opiekowali się bazylianie. Ale to już był czas rozbiorów Polski. Zamość zajęła Austria już podczas I rozbioru w 1772 r. Ostatecznie złe czasy dla cerkwi i bazylianów nastały, kiedy na skutek kongresu wiedeńskiego w 1815 r. Zamość przeszedł pod zabór rosyjski. Car Rosji nie uznawał Kościoła greckokatolickiego i wprowadził prześladowanie unitów. Ponadto świątynia zamojska od 1618 do 1824 r. pobierała od ordynatów 400 zł rocznie na jej utrzymanie i remonty. Ale w 1824 r. Zamość przestał być prywatnym miastem Zamoyskich, gdyż miasto przejął rząd rosyjski. Ustały wobec tego dotacje. Na skutek trudnej sytuacji materialnej i represji ze strony caratu zmniejszyła się liczba bazylianów opiekujących się świątynią. Z upływem lat cerkiew coraz bardziej ulegała zniszczeniu. Ks. A. Zienkiewicz, superior zamojskiego klasztoru bazylianów, w raporcie do biskupa chełmskiego Szumbowskiego 28 kwietnia 1841 r. donosił o katastrofalnym stanie cerkwi, pisząc: „Cerkiew zamojska, stojąc od kilkuset lat, czasami była reperowana i stała do 24 lipca 1840 r., przynajmniej nie grożąc upadkiem. Po dniu wspomnianym sklepienie i mury zarysowały się, a ustawiczne deszcze przez całe lato i jesień tak mury zrujnowały, że co chwila rozsypują się, cegły wypadają i zagrażają śmiercią dla ludzi”. W 1862 r. już tylko jeden ksiądz unicki pełnił obowiązki duszpasterskie. Ostatecznym posunięciem rządu carskiego było zlikwidowanie Kościoła unickiego w 1874 r. Od 1875 r. świątynia pw. św. Mikołaja w Zamościu stała się cerkwią prawosławną.
W 1915 r. Zamościem znowu zawładnęli Austriacy, którzy odebrali kościół prawosławnym i przekazali go katolikom z przeznaczeniem na kościół szkolny pw. św. Stanisława Kostki. Po odzyskaniu niepodległości bp M. Fulman, ordynariusz lubelski, przekazał w 1934 r. kościół Ojcom Redemptorystom, którzy wprowadzili kult Matki Bożej Nieustającej Pomocy. Po wybuchu wojny i zajęciu Zamościa przez Niemców już jesienią 1939 r. prawosławni przy pomocy okupanta siłą odebrali kościół, który ponownie stał się cerkwią. Chwalili Niemców za ład, porządek i sprawiedliwość zaprowadzone w Zamościu. W 1942 r. wypędzono Redemptorystów z kalsztoru, o. Pilarczyk został wywieziony do obozu koncentracyjnego w Dachau, a o. Wójtowicza i o. Jakubowskiego rozstrzelano na Rotundzie.
Po wyparciu Niemców z Zamościa w lipcu 1944 r. Redemptoryści ponownie objęli kościół w styczniu 1945 r. W latach 1981-94 był kościołem parafialnym. Od 23 marca 1994 r. kościół pw. św. Mikołaja jest kościołem zakonnym będącym pod opieką Ojców Redemptorystów.