Výstavba gréckokatolíckej cerkvi v Trebišove bezprostredne súvisela s vrcholiacou migráciou obyvateľstva zo severovýchodu horného Uhorska do úrodnejších častí Zemplína počas ruthénskej kolonizácie v 18. a prvej tretine 19. storočia. V roku 1720 tvorilo Trebišov iba 36 meštianskych domácností. Neobývané domy chátrali a polia zarastali burinou.
V matrike gréckokatolíckej cirkvi, vedenej od roku 1776, je správa o starej fare, ktorá naznačuje existenciu staršej cerkvi tejto východnej cirkvi v Trebišove. Môžeme len predpokladať, že pôvodná cerkev bola drevená so slamenou strechou a nepostačovala vzrastajúcemu počtu veriacich po jednotlivých migračných vlnách.
Preto bol v čase vrcholiacej migrácie 28. augusta 1817 položený základný kameň nového kamenného chrámu pre veriacich východného obradu. Projektantom novej gréckokatolíckej cerkvi bol staviteľ Jozef Turčáni. Navrhol chrám, ktorého interiér postačoval potrebám duchovného života vzrastajúceho počtu veriacich gréckokatolíckej cirkvi. Výstavba chrámu bola realizovaná v rokoch 1818 - 1825. Jeho slávnostná vysviacka sa uskutočnila 28. augusta 1825 na sviatok nanebovzatia Presvätej Bohorodičky. Bol to dôkaz toho, že v meste bolo veľmi silné patrocínium Panny Márie.
Tragické udalosti neobišli ani tento chrám. Živelná pohroma 3. júla 1844 spôsobila zrútenie kostolnej veže, ktorú znovu postavili v roku 1855. Po silnom požiari v roku 1876 boli zničené zvony vo veži, na ktoré prispel kráľ i ministerstvo kultúry. Obnova interiéru chrámu bola ukončená v roku 1886, keď bol rezbárom Petrom Kovaliczkým postavený ikonostas a kazateľnica.
Dominantnou ikonou na ikonostase je Smrť Panny Márie. Spolu s ňou sú tam umiestnené aj ikony Ježiša Krista, Matky Božej, Sv. Mikuláša. V ďalšom rade menších ikon je v centre Posledná večera a po jej obidvoch stranách je dvanásť hlavných cirkevných sviatkov kresťanského roka. Ikony dvanástich apoštolov, prorokov a patriarchov, nad nimi dominujúca Golgota s Bolestnou Matkou a Sv. Jánom Krstiteľom, dotvárajú kompozíciu celého ikonostasu. Prístavbou sachristie roku 1901, zakúpením umelecky hodnotného lustra, vydláždením interiéru keramickou dlažbou a osadením okenných vitráží (1907) bola dostavba chrámu prakticky ukončená. Namiesto troch zrekvírovaných zvonov z rokov prvej svetovej vojny bol v 20-tych rokoch 20. storočia zakúpený veľký zvon pomenovaný menom Georgij. Oplotenie s vykovanou ozdobnou vežou bolo ukončené a osadené roku 1903.
