В середине XIX века комендант Бендерской крепости генерал-лейтенант Марцеллин Ольшевский начал строительство первого в Бендерах католического храма святых апостолов Петра и Павла. К концу 1870-х годов здание передали православной церкви.
Во время Великой Отечественной войны (1941 — 1945 гг.) здание значительно пострадало и находилось в аварийном состоянии. В 1951 году его передали под нужды спортивной школы и провели реконструкцию. В последующие годы в здании размещалась также школа строителей, клуб, общежитие школы-интерната и лицей легкой промышленности.
9 июня 1997 году в результате ходатайства епископа Дубоссарского Юстиниана (Овчинникова) и многочисленных обращений прихожан здание храма вернули православной церкви.
Храм был принят в аварийном состоянии: протекающие крыши, сгнившая столярка, проржавевшая сантехника, провисающий потолок, отсутствие благоустроенных келий и т.п. За прошедшие годы была произведена реконструкция и благоустройство зданий и территории для нужд монастыря. Оборудованы кухня, трапезная, полностью изменён фасад и парадная лестница, построены швейный цех, церковная лавка, отдельное здание библиотеки, звонница с добавлением двух больших колоколов «Петра и Павла», благоустроен цветник, в центре которого установлено большое деревянное Распятие. Обновлена кровля.
В 2002 году при храме открыли Епархиальное духовное училище, воскресную школу и библиотеку. В то же время сформировалась община из 12 послушниц, а в 2006 году здесь открылся женский Петропавловский монастырь.
Основатель храма генерал-лейтенант Марцеллин Ольшевский скончался в 1866 году и был захоронен в усыпальнице на территории храма. В 1953 году его прах перенесли на кладбище. В самом монастыре в память о его основателе находится надгробная плита с могилы М. Ольшевского.
