Keď kanonik ostrihomskej kapituly Eusébius na základe príkladu svätého Pavla Pustovníka zjednotil v roku 1225 jednotlivo žijúcich pustovníkov, ešte netušil, že položil základy jediného pôvodne uhorského mužského rádu - pavlínov. Rád sa konštituoval v ostrihomskej arcidiecéze v roku 1256 a jeho existenciu potvrdil pápež Klement V. keď roku 1308 schválil jeho rehoľné pravidlá. Tak vznikal jediná pôvodne uhorská rehoľa pavlínov, ktorá malá svoj kláštor aj v Trebišove. Trebišov však vstúpil do dejín pavlínskeho rádu až po uplynutí takmer dvoch storočí od jeho vzniku. Jeden z najvplyvnejších Peréniyovcov Palatín Imrich dal roku 1502 postaviť v Trebišove dvojpodlažný kláštor. V roku 1504 doň pozval pavlínov, ktorým daroval so súhlasom panovníka aj dediny Sáros, Olaszi a vodný mlyn na Bodrogu.
Objekt renesančného kláštora v tvare písmena I bol južným krídlom priamo pričlenený ku kostolu. V niektorých jeho miestnostiach sa zachovali hrebienkové klenby. Mária Spoločníková objavila pod omietkami zaujímavé fragmenty. Pozoruhodné sú aj kamenné ostenia spojovacích dverí. Prostredie kláštora dotváral dvor so studňou a záhradou, ktorý bol súčasťou jeho života.
Kláštor bol v minulosti niekoľko krát obnovovaný. Priečelie obnovovali v rokoch 1678, 1720 pričom jeho členenie sa realizovalo roku 1876. Pôvodný kláštor mal na vonkajších múroch renesančné sgrafitá. Zrušením pavlínskeho rádu Jozefom II. Roku 1786 kláštor stratil svoje pôvodné určenie a bol využívaný na rôzne účely. V čase zániku kláštora predstavoval majetok siedmich mníchov žijúcich v kláštore 94 261 zlatých.
V súčasnosti sa v objekte kláštora nachádza základná umelecká škola a rímskokatolícky farský úrad.
