Новое каменное здание Богоявленского храма было возведено примерно в первом десятилетии XVIII века. К сожалению, ни в одном из известных исторических источников данный этап истории строительства храма не отмечен. Однако сами архитектурные формы его бесспорно свидетельствуют о том, что в камне Богоявленская церковь была построена не в середине XVII века, а позднее.

А когда же именно она была возведена? Наш храм отображен на чертеже, сделанном в 1700—1728 годах, уже как приходской. А по воспоминаниям одного из путешественников, побывавших в Орле в 1711 году, в обветшавшем уже деревянном городе «церквей каменных много» (Г. Пясецкий. История Орловской епархии. Орел: 1899, с. 265). Известно также, что в 1714 году вышел указ Петра I, запрещающий по всей стране каменное строительство в связи с возведением Санкт-Петербура. В провинции оно возобновилось лишь в 1770-х годах, когда, согласно документам, каменная Богоявленская церковь уже существовала. Тогда же, как сообщают «Орловские губернские ведомости» (1876, № 7, с. 38), каменная колокольня нашего храма из-за своей ветхости угрожала падением и уже в 1780 году требовалось её сломать.

Итак, можно сказать, каменная Богоявленская церковь в Орле была сооружена в первом десятилетии XVIII века. К тому же, в «Ведомостях о церквах города Орла» в течение последующего столетия этот храм идет вторым по списку после главного городского собора. Начиная с 1755 года в документах сообщалось и о наличии престолов в церквях. В Богоявленской к этому моменту имелся второй престол во имя Вознесения Господня. К 1787 году также появляется третий — во имя святых благоверных князей Бориса и Глеба (ЦГАДА, ф. 1355, оп. I, с.1009. Описание г. Орла /Экономич. примеч./, 1798 г., л. I об.). Трехпрестольным храм оставался до своей капитальной перестройки в первой трети ХIХ века.

Облик Богоявленского храма, наиболее близкий к первоначальному, предстает пред нами на рисунках и фотографиях — на них мы видим стройную, богато украшенную декором церковь. По стилистическим признакам ее можно отнести к так называемому «нарышкинскому барокко». Храмы этого архитектурного направления появлялись на рубеже XVII-XVIII веков в боярской среде, близкой к царскому двору. Множество таких строений было выстроено по заказу родственника Петра I, Л. К. Нарышкина. Это центрические ярусные строения со столпообразной композицией, за которыми в искусствоведческой науке закрепилось наименования «восьмерика на четверике». Они сочетали в себе живописность архитектурных форм с богатством декоративного убранства. Нарядность этих храмов еще более подчеркивалась их двухцветностью, изысканным сочетанием белого и красного цветов. Красные кирпичные стены оформляются резными белокаменными карнизами, орнаментальными сборками, наличники окон — фронтонами в виде гребешков, грани объемов по углам — белокаменными резными колоннами.

Богоявленский храм в Орле до своей капитальной перестройки относился к лучшим образцам «нарышкинского барокко». Он обладает всеми особенностями этого стиля: основной объем, трапезная, колокольня. Как отмечали архитекторы, немногие колокольни так органично дополняли храмы, как та колокольня Богоявленской церкви, соединяющая в себе изящество и величие.

Известный орловский архитектор С. И. Федоров сообщает в одной из своих работ, что в 1970 году он совместно с еще одним орловским краеведом произвел раскрытие на световом барабане церкви: «мы вскрыли под толстым слоем штукатурки… вырезанные из белого камня балясины, наличники и пояски, сходные по характеру обработки с декором основания колокольни (С. И. Федоров. Архитектурные образы Орловщины. Тула: 1982, с. 32). Он свидетельствует также:»При изучении наиболее сохранившегося светового барабана мною были обнаружены в 1959 году несколько голосников, отверстия которых были заштукатурены. Глубина глиняных горшков, замурованных в стены, составляла 40—60 см. Они… обеспечивали прекрасную акустику… церкви (С. И. Федоров, там же, с. 31).

Итак, каменный Богоявленский храм, построенный на месте деревянной церкви того же названия стал украшением города. Его празднично-торжественная архитектура, созвучная московским храмам этого времени, свидетельствовала об авторстве талантливого художника. Очевидно, яркая красота храма и центральное местоположение стали причиной того, что после упразднения обветшавшей соборной Рождественской церкви (в 1766 г.) в нем стали совершаться почти все торжественные городские богослужения. Уже в 1770 году Богоявленская церковь принимала в своих стенах орловского епископа. Мемуарист ХVIII века Г.Добрынин так описывает это событие: «…Въезд преосвященного в Орел ознаменован был по всем церквам колокольным звоном. При каждой проезжаемой церкви священство было в ризах со крестами, дьяконы в стихарях с кадилами, дьячки и пономари со святою водою в чаше, со свечами в подсвечниках. Народ — по улицам, народ — по заборам и по всем возвышениям, где только можно пристать и удержаться. А в Богоявленской церкви, в которую было ожидаемо восшествие Преосвященного, набилось всякого чина и звания, пола и возраста православных Христиан так плотно, как в Риге на кораблях укладывают мачты. По выходе из церкви поздравляли пастыря с приездом градоначальник со всеми чиновниками…» (Г. Добрынин. Истинное повествование или жизнь Гаврииила Добрынина (1752—1823). СПб., ч. I, с. 41—43).

Автор этого описания сообщает любопытную подробность о священнике Богоявленской церкви отце Алексее. В отличие от других священников и самого епископа он проявлял доброе отношение и веротерпимость по отношению к орловским купцам-старообрядцам. Во время упомянутого посещения города епископом они добились повышения  о.Алексея в сане, он стал протоиерееем. «Все знатнейшие старообрядцы упросили архиерея убедительнейшими способами возвысить в сие достоинство богоявленского отца Алексея…» (Г. Добрынин, там же, с. 43).

Тогда же в 1770 году орловский епископ издал указ о ликвидации кладбища при Богоявленской церкви: «Понеже во время посещения епархии в городе Орле усмотрено нами, что при градских церквах Богоявленской, Покровской и Пятницкой так тесны кладбища и телами мертвыми наполнены, что когда случается вновь погребать, без нарушения телес прежде погребенных, быть не может. Сверх того домы обывателей к оным весьма близко поселены, которые от оных кладбищ воздухом заразительным в весеннее особенно время наполняются невольно… того ради в Духовное правление посылается указ наш… чтобы отныне впередь, как вышеписанных церквей, так и других градских… погребать тела умерших при отдаленных несколько церквах, из которых одна по сю сторону, а другая по ту сторону реки были бы, чтоб через реку при погребении не переезжать» (Г. Пясецкий. История Орловской епархии. Орел.: 1899, с.651—652).