Nové proboštství na pražském Vyšehradě je novogotická stavba, která se nachází ve Štulcově ulici číslo 4 – tato ulice je mimochodem pojmenovaná podle Václava Štulce, velmi významného vlastence, který Nové proboštství nechal na konci devatenáctého století postavit.
Václav Štulc se narodil v roce 1814 v Kladně, ve třicátých letech absolvoval teologické studium a v roce 1839 byl vysvěcen na katolického kněze. Tento duchovní se ale nespokojil s relativně pohodlným životem představitele církevní a tehdy i tím pádem stále státní moci. Ačkoliv rakouský stát byl nerozlučně spjat s Vatikánem, Václav Štulc se cítil Čechem a vlastenectví věnoval velkou část svého života a také literární tvorby. Dokonce byl pro své tehdy přeci jen mírně protistátní postoje odsouzen na několik měsíců žaláře. Součástí jeho pronárodních postojů byla i velká starost o Vyšehrad. Tento hrad již byl delší dobu na okraji zájmu veřejnosti a při tom byl velmi výrazně spjat s českou státností. Václav Štulc proto v pozici vyšehradského děkana (a od roku 1871 i probošta) začal velmi výrazně pracovat na pozvednutí jeho tehdy dosti zaprášené slávy. Dnešní Vyšehrad je pro většinu lidí spojen se dvěma objekty. Jedním z nich je kostel Petra a Pavla, který spolu s barokním opevněním je druhým v dnešní době nejvýraznějším prvkem starého přemyslovského sídla a druhým je Slavín, pohřebiště našich nejslavnějších. Jak kostel, tak hrobky vznikly díky knězově iniciativě. A třetí záležitostí, o kterou se také zasloužil, je právě budova Nového proboštství.
Stavební plány nové proboštské rezidence byly navrženy pražským stavitelem a architektem Josefem Niklasem. Budova byla postavena v roce 1874, ale stavební firma nebyla příliš seriózní a původní rozpočet ve výši 35 000 zlatých byl výrazně překročen a nebyly dodržovány přislíbené termíny. V budově byla umístěna i kaple svatého Klimenta, kterou Václav Štulc po dokončení stavby vysvětil. Na konci třicátých a na začátku čtyřicátých let došlo k rekonstrukci stavby a další velká oprava přišla v letech 1993 až 1994