Kostel sv. Mikuláše byl založen kolem roku 1265 - pro stavbu kostela byla již při vyměřování města vyčleněna plocha jednoho celého bloku, navazující na severovýchodní roh náměstí. Kolem roku 1297 byl pravděpodobně dostavěn chór na východní straně, obě chórové kaple a posvěcen hlavní oltář. Vybudování tohoto farního chrámu se však zřejmě protáhlo, protože ještě v témže roce udělil cařihradský patriarcha Petr odpustky všem, kdo přispějí na stavbu, osvětlení a jiné nezbytnosti. Teprve kolem poloviny 14. století byla snad dokončena i stavba trojlodí a západního dvouvěžového průčelí se zaklenutou předsíní, nad kterou byla umístěna kruchta. V rozmezí od poloviny 14. století do počátku století 15. založili budějovičtí měšťané 17 vedlejších oltářů. V 16. století došlo k rozsáhlým přestavbám kostela, na jejímž konci byla mimořádně členitá a pohledově jistě velmi bizarní stavba známá a zachycená ne vedutě Jana Willenberga z roku 1602. Poslední velkou přestavbou prošel kostel v 1. polovině 17. století po požáru, který ve městě roku 1641 vypukl. V této podobě známe kostel s menšími úpravami dnes. V bezprostřední blízkosti okolí kostela se nacházel jeden z městských hřbitovů, který sloužil k pohřbívání zřejmě již od 13. století, a to zámožných budějovických měšťanů. Nejstarší písemná zmínka k tomuto hřbitovu pochází z roku 1377, která se zmiňuje o stavbě kaple sv. Jakuba na hřbitově, v 18. století přestavěná na Kapli Smrtelných Úzkostí Páně. Poslední pohřeb se na tomto hřbitově konal v roce 1784 a téhož roku byl hřbitov zrušen.