Петро-Павловский женский монастырь (древнее название — Петровский) был основан во граде Брянске Преподобным благоверным князем Олегом Брянским. Дату основания обители предание относит к 1275 году. Монастырь, находящийся на юго-западных рубежах России, неоднократно разорялся. К концу XVIII века в обители имелось два храма: каменный соборный в честь Введения во храм Пресвятой Богородицы и деревянный на Святых вратах во имя Пророка Божия Илии. Ограда монастыря к тому времени была каменная, длиною 230 погонных саженей, а настоятельские и братские келлии — деревянные. В монастыре помещалось и Брянское Духовное Правление. К обители были приписаны Брянский Поликарпов монастырь в честь Преображения Господня, Бело-Бережская и Полпинская пустыни, храм упраздненного Брянского женского монастыря в честь Вознесения Господня.
Согласно указу Императрицы Екатерины II от 26 февраля 1764 года монастырь был лишен всех вотчин и угодий, а к концу 1766 года возведен на степень 3 класса. 13 сентября 1830 года Император Николай I утвердил предложение Святейшего Синода о строительстве в Ельце мужского монастыря во Имя Святой Троицы и переводе туда штата монастыря во имя Святых Первоверховных Апостолов Петра и Павла, который объявлялся упраздненным, а храмы его — приходскими. Однако по прошению Брянского градского общества и ходатайству местных купцов Ивана и Козьмы Семыкиных, пожертвовавших средства на восстановление обители для вдов, девиц и сирот, 18 ноября 1833 года Государь разрешил восстановить в Брянске упраздненный монастырь и разместить в нем монахинь на правах общежития. В 1882 году в монастыре было 169 насельниц, в 1903 — 176, в 1910 — около 200. К 1917 году в обители было два храма, семь каменных, с деревянным верхом, корпусов и 30 деревянных флигелей-келлий.
Вскоре после октябрьского переворота в монастырских келлиях поселились рабочие Брянского арсенала, но обитель продолжала существовать. В июне 1923 года монастырь был закрыт. В храме во имя Пророка Илии устроили рабочий клуб, впоследствии переоборудованный под кинотеатр имени Демьяна Бедного, просуществовавший до 1974 года. Затем этот храм разрушили. Храм в честь Введения во храм Пресвятой Богородицы был разграблен и занят губернским архивом. Кладбище, на котором были погребены и известные жители города, разорили. В 1944 году было возобновлено приходское Богослужение в уцелевшем и при фашистских оккупантах храме в честь Введения во храм Пресвятой Богородицы. Оставшиеся в живых насельницы обители еще пели на клиросе и прислуживали в родном храме. По ходатайству Преосвященного Феофилакта, Епископа Брянского и Севского, определением Священного Синода Русской Православной Церкви от 7 октября 2002 года монастырь был возобновлен.
Монастырь основан ранее 1288 года, поскольку упоминается в легенде об основании Свенского монастыря (XVII века): в 1288 году слепнущий князь Роман Михайлович в надежде на исцеление послал в Киево-Печёрский монастырь за чудотворной иконой Божией Матери архимандрита. О древнейшей истории монастыря документальных свидетельств не сохранилось. В рукописных святцах XVII-XVIII веков говорится о том, что в монастыре был похоронен принявший монашеский постриг святой князь Олег Романович Брянский, из этого сообщения архиепископ Филарет (Гумилевский) сделал вывод, что святой князь являлся основателем обители. Синодики, которые отражают тексты старше XVII века (например, Любецкий), сообщая о пострижении князя Олега в монашество, ничего не говорят о месте его погребения. К началу XIV века в монастыре существовала деревянная церковь во имя апостолов Петра и Павла. К середине того столетия обитель пришла в упадок, неоднократно (в 1356,1534, 1583, 1609 годах) она разорялась литовскими войсками и запорожскими казаками. В 20-х годах XVII века монастырь отстроился, согласно писцовым книгам 1626-1629 годов, в монастыре существовали Петропавловская церковь, пять келий, обитель владела селом Городище с Благовещенской церковью на реке Десне и пашнями пустоши Лизовицы. Патриарх Никон возводил монастырь на степень ставропигии.
К началу XVIII в. деревянная Петропавловская церковь обветшала, и 25 апреля 1702 года брянские стряпчие Ф. и П. Саловы обратились в Патриарший приказ с просьбой о разрешении построить в монастыре новый храм для поминовения своих родителей. В том же году был возведен каменный собор в честь Введения во храм Богородицы с теплым приделом во имя апостолов Петра и Павла; в 1755 году по прошению купца И.А. Никулина в храме был устроен придел в честь иконы Божией Матери «Знамение». В 1781 году на святых вратах построили деревянную церковь во имя пророка Илии. В первой половине XVIII века монастырь владел сёлами Полпино, Городище на реке Десне, деревней Ходиловичи, мельницей на реке Снежети, земельными участками в Брянске, монастырю принадлежали 1423 крестьянина. На землях обители находились Полпинская и Белобережская пустыни, до 1764 года к монастырю был приписан Поликарпов монастырь, братия монастыря устроила несколько скитов в Брянском уезде. В 1766 году монастырь был причислен к третьему классу, до этого времени настоятели обители имели сан архимандрита, с 1766 года — сан игумена. В 1796 году монастырю было передано имущество упраздненного Брянского Вознесенского женского монастыря. При монастыре действовало уездное духовное училище, находившееся в ведении Орловской духовной семинарии.
В начале XIX века монастырь пришёл в запустение и указом Синода от 17 сентября 1831 года был упразднен с переводом насельников в новоучрежденный Троицкий монастырь в Ельце. 18 ноября 1833 года обитель восстановили как женский по ходатайству и на средства купцов И. и К. Семыкиных. При игумене Иринархе (1837-1854 годы) в монастыре были построены каменный келейный корпус, деревянный флигель, каменная ограда, увеличилась территория монастыря. При игумене Амфилохии (1854-1871 годы) вместо обветшавшей Ильинской церкви на святых вратах был воздвигнут двухэтажный Ильинский храм с четырьмя престолами: верхними — в честь Сретения Господня и во имя великомученицы Екатерины и нижними — в честь Владимирской иконы Божией Матери и во имя пророка Илии; возведены два каменных келейных корпуса. 18 ноября 1875 года при монастыре открылась школа, где бесплатно обучалось до 100 девочек. На средства купцов Могилёвцевых в 1905 году в монастыре устроили водопровод, в 1911 году был поставлен больничный корпус. В 1914 году в больнице и гостинице монастыря разместился военный госпиталь. В 1836 году в монастыре жили 14 насельниц, в 1871 году — 161, в 1917 году — 176 монахинь и послушниц, к этому времени монастырь владел 108 десятинами земли.
Мощи святого князя Олега Брянского, главная святыня монастыря, первоначально почивали под спудом на территории обители. 14 ноября 1893 года великий князь Константин Константинович пожаловал монастырю икону святого князя, позолоченную лампаду и 600 рублей. Другой святыней была местночтимая Казанская икона Божией Матери — копия с чудотворного образа, вложенного в 1620 году царём Михаилом Феодоровичем в Площанскую пустынь. В монастыре хранился также резной образ святого Николая Чудотворца, перенесенный из сгоревшей Николаевской церкви Брянска.
В декабре 1918 года указом Брянского уездного исполкома монахини были выселены из монастыря, в кельях поселились рабочие Брянского арсенала, храмы были закрыты. В ходе кампании по изъятию церковных ценностей из монастыря было конфисковано большое количество богослужебной утвари. Монастырь был окончательно закрыт указом Брянского исполкома 1 июня 1923 года, кельи были отданы под квартиры рабочим и общежитие для учащихся, несколько корпусов заняла прачечная, обслуживавшая военный гарнизон. В Ильинской церкви устроили рабочий клуб, впоследствии переоборудованный под кинотеатр, затем храм разрушили. В Введенском храме разместился губернский архив, главы собора и колокольня были разобраны. В начале 30-х годов XX века при Брянском епископе священномученнике Данииле (Троицком) были обретены и перезахоронены под алтарем Введенской церкви мощи святого князя Олега, в 1944 году Введенский храм был открыт как приходской, бывшие насельницы монастыря прислуживали за богослужениями. 10 августа 1995 года состоялось второе обретение мощей святого князя Олега, которые в настоящее время открыто почивают в монастырском Введенском храме.
Решением Священного Синода от 7 октября 2002 года монастырь был открыт как женский, настоятельницей назначена инокиня Сергия (Ёжикова), переведенная из Александровского в честь Успения Божией Матери монастыря. К июню 2003 года в монастыре живут три инокини, бывшие насельницы Одрина монастыря. Богослужения совершаются в отреставрированной Введенской церкви. Монастырю принадлежат сестринский корпус и хозяйственные помещения, часть территории обители с игуменским корпусом занимает кожно-венерологический диспансер.