Первые католические церкви появились в Великом Новгороде в XI — XII веках, это были не сохранившиеся до наших дней церковь св. Олафа для купцов с Готланда и церковь св. Петра для немецких торговцев. После присоединения Новгорода к Москве в 1494 году, католический храм некоторое время функционировал, однако, в XVI веке немецкая община в городе почти исчезла и католических храмов в городе не было вплоть до XIX века.

В XIX веке в город переселилось большое количество людей католического вероисповедания из Польши и Прибалтики. В 1838 году в Новгороде была построена католическая часовня.
Католиков ещё более выросло за счёт сосланных в Новгородскую губернию участников польского восстания 1863 года и в 1874 году городская католическая община построила деревянную церковь, которая пятнадцатью годами позже сгорела до основания.


Католический священник Феликс Пиотровский бросился в пылающий деревянный костел за Святыми Дарами и вынес их из огня. Подвиг вызвал огромный поток пожертвований на постройку новой церкви. Проект каменного храма польского архитектора Р.К. Кржижановского утверждён в 1891 году, а 1893 году храм был освящён во имя святых Апостолов Петра и Павла.


Главный вход храма был оформлен овальной аркой с полуциркульным фронтоном, по бокам сооружены две колокольные башни с вогнутыми стенами. Каждую из них венчали фигурные шпили. В 1904 году при костеле было учреждено римско-католическое благотворительное общество, а тремя годами позже открылся детский приют.


В советское время в храме были разобраны колокольни и открыт кинотеатр "Родина".
В 1996 году здание костела было полностью передано Церкви. После реставрационных работ в храме святых апостолов Петра и Павла были возобновлены богослужения.


В 2010 году было завершено восстановление колоколен храма.
Храм обладает богатой библиотекой духовной литературы. Кроме того, в нем регулярно, по воскресеньям проводятся концерты органной музыки.