Год первоначальной постройки этой церкви неизвестен. В Вологодских Епархиальных Ведомостях № 15 за 1879 год была опубликована статья «К истории Вологды». Там написано:
«Где первоначально находилась и когда перенесена на нынешнее место Петропавловская церковь въ г. Вологда?
В первой половине XVI веке церковь эта находилась на берегу р. Вологды между семинарией и устьем реки Золотухи, где ныне каменное здание, бывшее прежде винным магазином. Отсюда она в 1560 годах, когда Царь Иоанн Грозный начал строить в Вологде каменную крепость, была перенесена в Новинскую улицу, а место, где находилась она и где стояли дома церковнослужителей, было занято строительными материалами для крепости. Сведение это найдено в Писцовой книге 1627 года: во время составления этой книги на этом месте находились два двора московских торговых людей Юдиных и Бехтеяровых. Вот подлинные слова Писцовой книги:
«От речки Золтухи по берегу внизъ р. Вологды дворъ московскихъ гостей Ивана да Василия Юдиныхъ, вдлину 60, поперегъ 22 сажени, да дворъ московскихъ же гостей Меншова да Семена да Бехтеяра Булгаковыхъ; вдлину 56, поперегъ 30 сажень, а прежде того на томь месте была церковь св. Апостоловъ Петра и Павла и стояли поповские и церковниковъ дворы. И блаженные памяти Государь Царь и Великий Князь Иванъ Bacильeвичь всеа Русии, какъ учалъ было на Вологде городъ каменный делать, и та церковь въ те поры перенесена въ Новинки, а то церковное место и церковниковъ дворы очищены были городовыхъ каменныхъ запасовъ, а на берегу передъ теми дворами лежит Государева известь, что вожена была для городского каменного дела...»
Там, где располагалась Петропавловская церковь, находилась слобода Новинки (от пристани до ул. Левичева). Здесь жили зажиточные люди и приезжие купцы.
Новинками слобода именовалась потому, что при ее образовании многие строения в исторической первой части города близ Софийского собора и Ленивой площадки были разобраны и перенесены на новое место. Так в 1560-х годах и Петропавловская церковь была перенесена в указанный район.
Более двухсот лет Петропавловская церковь оставалась деревянной. В 1772 году обветшалую деревянную церковь снесли и построили каменную. Она была одноэтажной, трехпрестольной. Колокольня приятных пропорций состояла из четырехгранной и восьмигранной призм. Среди мотивов убранства были и новшества: фигурные пилястры, зигзагообразные наличники на окнах и пр.
В начале 1930-х годов церковь частично разрушили: снесли колокольню и главки. Впоследствии в здании Петропавловской церкви был оборудован макаронный цех хлебокомбината. В настоящее время храм почти полностью разрушен. /См. фото/. В последние годы при разрушенном храме начала собираться община. Многие вологжане признают необходимость восстановления храма.
