Děkanský kostel sv. Mikuláše a P. Marie stojí v čele trojúhelníkového náměstí. 

Podle farní pamětnice v Rožmberku nad Vltavou (někdejším Nižším Brodě) byla plebánie již v roce 1150. Zřejmě zde stávala dřevěná kaple nebo kostelík, který patřil k faře Zátoň. První písemný údaj o kostele v Rožmberku pochází až z roku 1277, kdy potvrdil biskup Jan nadání manželky Voka z Rožmberka na zdejší kostel a v oce 1279 Jindřich z Rožmberka odevzdal farní správu vyšebrodskému cisterciáckému klášteru.

Stavba nynějšího farního kostela sv. Mikuláše byla dokončena zřejmě počátkem 14. století, pozůstatkem je jižní portál lodi, snad část obvodových zdí a spodek věže. Po skončení husitských došlo od poloviny 70. let 15. století k velkorysé pozdně gotické znovuvýstavbě kostela, která znamenala náhradu většiny částí stavby. Přestavba trvala více než jedno století a je důkazem dlouhého přežívání formálně gotických prvků v české sakrální architektuře.

V roce 1465 posvětil Sigmund Pirchan hlavní oltář a loď byla zaklenuta v roce 1480. Již v roce 1488, byl kostel znovu zaklenut. Nejspíše se však jednalo o zaklenutí chrámové lodi. Podle zápisů vyšebrodského kláštera získal kostel trojlodí se síťovou klenbou dokonce až roku 1583 (nákladem vyšebrodského opata Georga Taxera). Jako většina českých kostelů byl i farní kostel v Rožmberku od husitských dob do doby násilné rekatolizace po roce 1621 v rukou kněží pod obojí.

V roce 1664 byl znovu vysvěcen vyšebrodským opatem Jiřím Windschuhem. Tehdy měl kromě hlavního oltáře i čtyři postranní: oltář Panny Marie, svatého Václava, svatého Štěpána a svatého Linharta. V roce 1762 byl hlavní oltář vyměněn za nový.

Stavební podstatu kostela nezasáhly žádné další úpravy, jen při restauraci roku 1881 byla zničena většina kamenických značek. V roce 1893 byly dány nové varhany a v roce 1900 zřízeny místo barokních nové postranní oltáře v gotickém slohu. Mezi severním bokem kněžiště a východní zdí kostela je vestavěna mohutná věž s točitým schodištěm. U obou bočních vchodů jsou předsíně, stejně jako u kněžiště, odkud je vchod na oratoř.