Le monastère de Pierre et Paul à Mtsensk a été fondé à l'emplacement de l'ancien petit fort de la forteresse de Mtsensk. On considère qu'il est l'un des plus anciens monastères de l'Orlovschina et, selon la tradition, a été fondé au XIIe siècle. Cependant, il est plus probable que sa fondation remonte au début du XVIe siècle, lorsque Mtsensk est entré dans le territoire de l'État de Moscou en 1500. À l'origine, le monastère s'appelait monastère de Pierre.

En 1694, le monastère de Pierre a été transféré à un nouvel emplacement en aval de la rivière Zousha et a été renommé monastère de Pierre et Paul. La construction du monastère à ce nouvel emplacement, sur des terres offertes par les nobles Protasov (actuel quartier de la gare), a commencé en 1695. L'abbé Herman a posé la première pierre de la cathédrale de la Protection avec une chapelle dédiée aux saints apôtres Pierre et Paul, dont la construction s'est poursuivie au début du XVIIIe siècle. Grâce aux efforts des donateurs et des moines, le monastère a été entièrement reconstruit et aménagé d'ici le milieu du XVIIIe siècle. Selon l'inventaire de 1764, son territoire comprenait deux églises : la cathédrale de la Protection et l'église en bois de la Rencontre du Seigneur, ainsi que les cellules des supérieurs et des frères, une boulangerie, un entrepôt et une cave. Le monastère était entouré d'une clôture en briques d'environ 350 mètres de long avec des tours et des portes, construite grâce aux efforts de l'abbesse Anfisa et de l'abbé Théodule. En dehors de la clôture se trouvaient un jardin, des potagers et une cour économique. Le monastère possédait le village d'Igoumnova Slobodka avec 74 paysans.

Deux écoles fonctionnaient au monastère, où 151 garçons étaient instruits. C'était l'un des premiers établissements d'enseignement dans la région d'Orlov. Bien qu'il n'y ait pas eu officiellement d'hospice, le monastère entretenait deux soldats blessés, participants aux guerres contre la Turquie et la Prusse. En 1764, les terres du monastère ont été confisquées et il a été retiré du statut. En 1819, après le transfert du siège épiscopal de Sevsk à Orel, le monastère a été rétabli dans le statut et ses supérieurs ont été élevés au rang d'archimandrites.

À la fin du XVIIIe et au début du XIXe siècle, une construction active a eu lieu au monastère, modifiant son apparence. L'église en briques de la Protection (1813-1821) a été construite, une immense cloche (1807) a été érigée, presque tous les bâtiments du monastère ont été rénovés ou reconstruits, et la clôture a été refaite. La cathédrale de la Protection a été peinte, les iconostases ont été renouvelées, et en 1809, une galerie avec une sacristie et une bibliothèque a été aménagée à l'emplacement de l'ancienne cloche. À côté de la cathédrale, un cimetière a été créé, où étaient enterrés les donateurs du monastère et des citoyens respectés. Y ont été enterrés les Protasov, les Khovansky, les Menshikov, les Yusupov et d'autres, ainsi que de nombreux moines et abbés. En 1891, le général N. A. Bely a été enterré ici. En 1839 et 1846, le moine Melchisédek a vécu au monastère, dont l'activité ascétique a servi de base à la proposition de sa canonisation en 1918, mais celle-ci n'a pas été réalisée en raison des temps difficiles pour l'Église orthodoxe russe.

Les principales reliques du monastère étaient quatre icônes miraculeuses : celle du Christ Sauveur, celle de la Mère de Dieu de Tolga, celle de la Mère de Dieu de Koursk et celle de la Mère de Dieu de Tikhvine. La bibliothèque du monastère conservait un Évangile manuscrit du XVe siècle, un Trefologion de 1638 et un Évangile de 1694.

Le monastère a été fermé en 1923. Dans les années 1930, il a été utilisé comme prison pour les paysans dépossédés et est parvenu jusqu'à nos jours dans un état fortement dégradé. L'église de la Protection (sans ses finitions), le corps des cellules et les vestiges de la clôture ont été préservés. De l'ancienne cathédrale de la Protection, seules les absides de l'autel ont survécu.