Труды по управлению обширною епархией, заботы и огорчения подломили силы и здоровье маститого митрополита: на 26 июля 1691 года преосвященного Павла внезапно постигла болезнь – паралич, отнялся язык и память, правая рука и нога. В таком положении оставался он до конца августа того же года, а в следующем, 1962 году, по указу Государя, вызван в Москву, куда отправился больной, и по пути скончался 4 января 1692 года.
Для успешного распространения в этом крае христианства, по благословению патриарха Иоакима, основан был Селенгский монастырь (1681). В апреле 1683 года было заложено первое каменное здание – Софийский собор, прообразом которого явилась церковь Вознесения в Московском Кремле. Софийско-Успенский собор соорудили в 1686 году. Почти одновременно, в 1685-1686 годах вокруг Софийского двора построили каменную стену. В ее северной части находился главный вход, Святые ворота с Церковью Сергея Радонежского над ними. Тогда же построили и колокольню. Жилые же здания двора долго оставались деревянными, за исключением двухэтажного архиерейского дома. В 1700 году в бескрайней Тобольской епархии было 160 православных храмов. Но правильно организованных миссий для проповеди христианства в Сибири в этот период не было. Язычников, несмотря на успехи веры Христовой, оставалось еще много, и просвещение их было делом будущего.
Петр 1 был крайне заинтересован в обращении инородцев Сибири, поэтому его внимание привлекла деятельность почти душевнобольного Тобольского митрополита Игнатия Римского-Корсакого(1692-1701;фактически до 1699года), на которого в Москву непрерывно поступали жалобы. Стоит заметить, что митрополит Павел обличал Тобольского воеводу боярина Андрея Федоровича Нарышкина, который был двоюродным дядей, царствовавшего тогда Царя Петра 1. Злоупотребляя своею властью, воевода с дружиною творили всевозможные бесчинства: жили распутно, грабили народ и в особенности инородцев, истязали их. 18 июня 1700 года Петр попросил Киевского митрополита назначить на Сибирский митрополичий престол ученого монаха, «благого, непорочного жития человека, которому бы в Тобольске быть митрополитом, и мог бы Божиею помощию исподволь в Китае, и в Сибири в слепоте идолослужения и в прочих неверствиях закоснелых человек приводить в познание и служение, и поклонение истинного Живого Бога». В помощь этому человеку надо прислать ученых монахов, «которые бы могли твердыми святого Евангелия доводами многие души области темные сатанинские привести в свет познания Христа Бога нашего».
После этого 23 марта 1701 года малороссийский архимандрит Димитрий Туптало был посвящен в митрополита Тобольского и Сибирского. Однако царю так понравился этот образованный человек и прекрасный проповедник, что он не отпустил его в Сибирь, а сделал митрополитом Ростовским. Следующим кандидатом, предложенным Киевским митрополитом, был архимандрит Филофей Лещинский, который управлял Сибирской епархией в 1702-1711, а потом еще раз в 1715-1720 годах. Его-то и должно назвать основателем миссии в Западной Сибири. Трудности миссионерства в Сибири намного превосходили те, с которыми вынуждены были бороться проповедники православия в Европейской России. Удаленность от главных церковных и светских центров столицы затрудняла служебную переписку. Духовенство, подчиненное митрополиту, не являло собой, как правило, образец нравственности и христианских добродетелей, да и не отличалось образованием. Немногие соглашались добровольно отправиться в далекую землю, где условия жизни духовенства были значительно хуже, чем в других российских епархиях. Многие священники, диаконы и монахи в наказание за какие-нибудь проступки ссылали в Сибирь и покидали эти края при первой же возможности. В XVIII веке в Святейший Синод постоянно приходили жалобы от Сибирских епархиальных архиереев на непригодность подчиненного им духовенства. Клирики совершенно не знали языков инородцев, но даже знания разговорного языка не помогало в переводе христианских понятий, которым не находилось соответствия не только в языке, но и в представлениях инородцев. Разнообразие религиозных исповеданий составляло еще одну специфическую трудность для миссии в Западной Сибири. Народности, находившиеся ранее под господством татар, частично исповедовали ислам. Между Уралом и Енисеем и далее на восток кочевали народы, приверженные самому примитивному шаманизму, который на юге, в Забайкалье, на монголо-китайской границе, смешивался с буддизмом-ламаизмом. Миссионеры сталкивались здесь с враждебным отношением населения ко всему русскому. Их совсем не поддерживали местные государственные власти, авторитет которых был в XVIII веке ничтожен: российская власть над инородцами в удалении от городов или крепостей во многих случаях существовала только на бумаге. При таких условиях миссия нуждалась в сотрудниках, которые были бы готовы на самопожертвование.
Митрополит Филофей, известный в Орловской губернии Свенского монастыря и строгий аскет, с большим усердием взялся за миссию в Сибирской епархии. Поначалу он хотел основать славяно-латинскую школу для полготовки миссионеров, но Петр I счел латынь излишней и отказал в деньгах, возложив финансирование школы на Тобольскую епархию, средства которой были и без того весьма скромными. Тогда Филофей предложил царю выселить татар-мусульман из епархии и ввести смертную казнь для многочисленных староверов, искавших убежище в Сибири, если они откажутся вернуться в Церковь. Миссионерская деятельность, по его убеждению, должна активизироваться прежде всего денежными поощрениями и льготами в налогах. Возможно, эти предложения 1702 года и стали причиной появления упомянутых указов царя о льготах для новокрещеных, которые действовали затем и в Сибири. Филофей управлял своей епархией дважды: в 1702-1711 и в 1715-1720 годах. Миссия первого периода сосредоточилась главным образом в области Березова, довольно близко к северу от Тобольска, на Иртыше и Оби. По личным указам Петра I от 1 декабря 1705 года и от 7 июня 1710 года миссионеры обращали в православие тамошних остяков, самоедов и вогулов, находившихся под властью шаманов, император повелел сжигать идолов, а новокрещеным в виде поощрения выдавать одежду и зерно за государственный счет. Митрополит Филофей вынашивал еще более грандиозные планы: так, в 1702 году он поставил задачу подготовить миссию в Китае и на Камчатке. В 1709 году он заболел и отправился на покой в монастырь, где принял схиму под именем Феодора, однако до прибытия в середине 1711 года своего преемника Иоанна Максимовича он продолжал прежнее служение, митрополит Иоанн, исполняя указ 1710 года по усилению миссионерской деятельности, просил его просвещать инородцев и далее. Филофей согласился и даже на покое, и во второй период своего служения отдавал все силы этой работе. Он лично ездил к остякам на Обь и Иртыш, посещал на юге зырян и вогулов, а также поселки мусульман и татар. Устав от миссионерских трудов, он в 1721 году окончательно оставил архиерейский престол и ушел в монастырь. Но и здесь он трудился для миссии вплоть до своей кончины в 1727 году; его главной заботой было укрепление новокрещеных в вере и окормление их, он строил храмы и старался воспитать хорошее духовенство. В пору его предстоятельства крестили примерно 40000 инородцев разных народностей Западной Сибири.
Повествуя истории Тобольско-Тюменской епархии необходимо рассказать о жизни великого просветителя Сибирской земли, святителя Иоанна, митрополита Тобольского и всея Сибири, чьи мощи до сей поры почивают под сводами Покровского собора. Святитель Иоанн родился в декабре 1651 года в Нежине, Черниговской губернии, и принадлежал к дворянскому роду. У отца его Максима Васильковского, жившего в Киеве и употреблявшего свои средства на украшение храмов Божиих, было семь сыновей, из коих Иоанн был старшим. Он выделялся из среды своих братьев особыми духовными дарованиями и прилежанием к книжному обучению. Закончил свое образование Иоанн в Киевской академии – единственной в то время на Руси школе высшего богословского знания. По окончании учения оставлен был при академии учителем, но душа его от юности стремилась к Господу. Прослужив восемь лет – с 1668 по 1676 год – в академии, Иоанн, желая посвятить себя иноческой жизни, принял в Киево-Печорской Лавре пострижение с именем Иоанна, затем был рукоположен во иеродиакона и иеромонаха, за свой выдающийся проповеднический талант получил звание проповедника и был затем любившей его монастырской братией избран на ответственную должность эконома Лавры.
Черниговский архиепископ святой Феодосий Углицкий, зная Иоанна Максимовича, как человека строгой подвижнической жизни, и предчувствуя близость своей кончины, вызвал его к себе в Чернигов и в половине 1695 года посвятил его в архимандрита Елецкого монастыря, которым до того времени сам управлял, готовя в новом архимандрите достойного себе преемника на святительскую кафедру в Чернигове. Вскоре (5 февраля 1696 года) святитель Феодосий почил о Господе. Преемником ему народом и властями единогласно был избран архимандрит Иоанн Максимович, рукоположенный 10 января 1697 года в Москве патриархом Андрианом в архиепископа Черниговского.