Děkanský kostel je zmiňován jako farní již roku 1280. Po založení kláštera augustiniánů v roce 1367 byl kostel přestavěn v gotickém slohu. V té době zde zanechal své jedinečné dílo patrně nejvýznamnější malíř gotické deskové malby v Čechách, Mistr Třeboňského oltáře. Dochované desky třeboňského oltáře jsou v současné době součástí sbírek Národní galerie v Praze. V gotickém kostele s dvoulodní dispozicí se zachovala světoznámá Třeboňská madona z doby kolem roku 1400. Křížová chodba, která přiléhá k severní straně kostela, se uchovala s téměř neporušenými freskami a rajským dvorem se studnou.
Zajímavost
V roce 1723 vypukl v Třeboni požár, který zničil téměř celé město a poškodil také kostel. Zřítila se klenba v presbytáři a požár zničil interiér kostela. Požár přečkaly fresky a socha Třeboňské madony. Nové řešení interiéru po požáru bylo svěřeno vídeňským umělcům P. Koeckovi (presbytář s hlavním oltářem) a J. N. Rottmayerovi (vlastní prostor kostela).