Церковь была построена в 1703-1708 годах как главная церковь Введенского девичьего монастыря, основанного в 1685 году. В середине XVIII столетия это был каменный двухпрестольный храм, покрытый тесом. Рядом стояла колокольня с часами. В 1829-1833 годах капитально перестроена: возведен второй этаж, первый этаж сделан теплым, вся церковь была покрыта железом, были сделаны новые полы и потолки. С 1793 по 1843 год в церкви служил известный орловский правдолюбец и ревнитель веры, духовник монастыря протоирей Лука Маликов. В 1843 году монастырь сгорел и был перенесен на другое место. Церковь после ремонта и реконструкции обращена в домовую церковь епархиального женского училища. Она была закрыта в 1923 году и передана под клуб Кожтреста. Здание церкви сгорело в ночь с 3 на 4 октября 1941 года. На этом месте в настоящее время располагается типография "Труд".