Pôvodný kostol je datovaný ešte pred rokom 1404. Napriek tomu, že súčasný rímskokatolícky chrám čiastočne ovplyvnili neskoršie umelecké a filozofické prúdy, patrí medzi skvostné pamiatky gotickej architektúry. Kostol má hlavnú loď a neskôr pristavené bočné kaplnky. Sieťovú rebrovú klenbu tvorí 63 polí v tvare kosoštvorcov rôznych veľkostí, s figurálnymi a dekoratívnymi motívmi. Interiér chrámu dotvárajú viaceré oltáre, nástenné maľby a triumfálny oblúk, pri ktorom sú plastické maskarony a konzoly. Na strope svätyne zobrazené scény zo života Panny Márie. Keďže správa o pôsobení kňaza Petra v Trebišove je z roku 1326, možno predpokladať, že na mieste staršieho kostola postavili pred rokom 1404 v gotickom slohu nový kostol. Tento bol do roku 1504 farským kostolom. Keď však Imrich Perényi pozval do Trebišova pavlínov (1504) začal kostol patriť v rokoch 1504 - 1530 a 1650 - 1786 mníchom z tohto rádu. Počas ich pôsobenia v Trebišove bol roku 1696 kláštorný kostol obnovený a neskôr (1770) interiérovo dotvorený.
Na pôvodných neskoro gotických klenbách interiéru je kvalitne stvárnený nebeský priestor s dekoráciami iluzívnej maľby z poslednej štvrtiny 18. storočia. Strop svätyne tvorí osem kompozícií zo života Panny Márie, ktorej je kostol zasvätený. Dvanásť obrazov z legendárneho života sv. Pavla Pustovníka tvorí strop lode. Bočné steny lode skrášľujú dva monumentálne obrazy: Videnie Sobieskeho pri obliehaní Viedne a Hold pred Máriou Teréziou, ktoré sú z roku 1777 a patria do obdobia rokoka. Povrchná, hrubá obnova malieb po požiari kostola a časti obce v roku 1876, reštaurátorské práce z donácie grófa Teodora (Tivadara) Andrássyho, obnova fresiek na vnútornej klenbe kostola v roku 1933 maliarom Júliusom Kernom, miestne premaľby poškodených častí v kartušiach, ornamentoch a kamenných článkoch spôsobili, že figurálne kompozície na viacerých miestach stratili svoj pôvodný kolorit spráškovatením horných vrstiev a hrubými nánosmi tmelov a miestnych premalieb v neskoršom období.
Podľa správy reštaurátorky Márie Spoločníkovej opravy uskutočnené v roku 1968 Umeleckými remeslami z Bratislavy a Chrámovým družstvom z Červeného Kostelca spôsobili, že ťažko rozpustné dvojzložkové spevňovacie látky môžu pri ďalšom reštaurovaní spôsobiť porušenie pôvodných omietkových vrstiev. Reštaurátorka usudzuje, že pod vyrovnávacími omietkami z roku 1777 existuje spodná vrstva neznámej nástennej maľby, ktorá bola realizovaná na pôvodný gotický strop.
Po prvej svetovej vojne bolo nutné nahradiť zrekvírované zvony a poškodené vežové krytiny. V rímskokatolíckom kostole zostal len najväčší zvon, ku ktorému v roku 1924 umiestnili dva menšie zvony zvonolejára E. Ferencza z Kisgejocso. V roku 1926 bol opravený aj posun oporného piliera na južnej strane gotického kostola. V tom čase bola nanovo pokrytá strecha veže a osadený nový kríž na jej vrcholci.
Pri vchode do sakristie sú umiestnené dva mramorové epitafy Jána a Imricha Perényiovcov. Ján Perényi má epitaf z hnedo-ružového mramoru so symbolikou, ktorú tvoria dve orlie krídla, hlava muža, rytierske brnenie, kukla s korunou a latinský nápis na stuhe náhrobku. Náhrobný kameň Imricha Perényiho, ktorý zomrel roku 1519, zobrazuje zakladateľa Trebišovského kláštora stojaceho v brnení na chrbte leva, opierajúc sa o meč a podporu štyroch anjelov. V ďalších kryptách pod podlahou kostola sú okrem Perényiovcov pochovaní aj Peter Szapáry, Etela Szapáryová a Júlia Csákyová.
V interiéri kostola sú aj ďalšie cenné umelecko-historické pamiatky: Závesné obrazy Navštívenie Panny Márie (1780), Svätý Pavol Pustovník (Koniec 18. storočia), Svätý Justín Mučeník (1835), Kamenná krstiteľnica (koniec 18. storočia) a pseudo-rokokové kreslo. Podľa zápisu v kronike mesta boli v okolí Trebišova v roku 1887 veľké manévre, na ktorých sa zúčastnil cisár František Jozef I. Gróf Július Andrássy dal na počesť cisára bývajúceho v trebišovskom kaštieli vyrobiť vyrezávané drevené kreslo s bohatou mušľovou i rozviliovou výzdobou a postavami anjelov. Tento „cisársky trón" je skutočne pozlátený plátkovým zlatom a čalúnený purpurovým plyšom v štýle pseudorokoka (druhého rokoka) druhej polovice 19. storočia. Gróf Teodor Andrássy ho neskôr daroval rímskokatolíckemu kostolu.
Stiahnutím stropu a múrov kostola železnými tiahlami, osadením malého zvona namiesto prasknutého do veže kostola majstrom zo Sopronu, položením vzorovanej keramickej dlažby (1901 - 1903), chrámových okien zo sklomaľbami Waltera Gidu a výstavbou kazateľnice Sopronským sochárom Leopoldom Hildom (1907) bol kostol staticky zabezpečený a interiérovo ukončený.
