Прибувши в Тобольськ і познайомившись зі станом справ у єпархії, святитель Павло визначив для себе кілька стратегічних напрямів. Перше, чим він старанно зайнявся, було просвітництво. Колишній викладач Київської Академії та проповідник Московської Академії відразу звернув увагу на семінарію при архієрейському будинку. Заснована ще 1702 р. митрополитом Філофеем (Лещинським), на час приходу святителя Павла в Тобольськ вона занепала. Це, певне, була єдина семінарія Руської Церкви, яка не мала повного курсу навчання. У ній не було вищих класів філософії та богослов’я. Таке становище можна пояснити великим браком кандидатів на церковні посади, через що ніколи було чекати закінчення повного курсу навчання.7
Проте головною причиною занепаду семінарії була відсутність державного фінансування. Згідно з Духовним регламентом, духовні школи вважалися школами при архієрейських будинках. Єпархіальні архієреї мали дбати про відкриття шкіл і утримувати їх на місцеві кошти. Тому стан духовної освіти в тій чи іншій єпархії залежав, переважно, від особи єпархіального архієрея. Тобольська єпархія, хоча за територією була й найбільшою, але далеко не багатою. Утримувати на свої кошти семінарію архієреєві було практично неможливо. Святитель Павло подає прохання в Святійший Синод про надання їй статусу штатної семінарії, але тільки 1765 р. домігся дозволу на отримання для неї 490 рублів на рік.8
Відкривши відсутні два класи — богослов’я та філософії — вчений ієрарх сам особисто і безпосередньо контролював викладання уроків. Збільшивши кількість семінарських предметів, ревний архіпастир почав дбати про збільшення складу її викладачів. Звертається він до рідного Києва, й не стільки до Академії, скільки до Києво-Печерської Лаври, яка завжди мала вільних учених ченців. Після зволікань, нарешті прохання сибірського святителя задовольнили й у січні 1764 року в Тобольськ відіслано двох учених ієромонахів: Саватія Ісаєвича й Веніаміна Бєлковського.9
Крім піклування про семінарію, яка мала виховувати грамотних пастирів-місіонерів, святитель задумав заснувати цілу мережу нижчих духовних училищ. Так, у 1759—1764 рр. у Тобольській єпархії було засновано низку так званих «заказних» шкіл, розташованих у «заказах». Це були школи в Барнаулі та Троїцьку, 1760 р.— у Красноярську й Верхотур’ї, 1761 р. — у Єкатеринбурзі, Далматові, Рафаїлові. Пізніше відкрилися школи й в інших заказах — Тарському, Томському, Самарівському, Ішимському, Туринському. Ці школи мали чотири класи: фари, інфіми, граматики й синтаксими. Після них учні мали вступати в піїтичний клас семінарії.10
Святитель Павло усвідомлював також важливість будівництва нових храмів для поширення християнства на території Сибіру. Він наполягав, аби будувалися камінні церкви. Разом з тим, намагався навести порядок із процедурою оформлення церковного будівництва, а також із збиранням коштів на будівництво нових храмів. Так, 1759 р. по духовних заказах було розіслано указ; у ньому докладно перераховувалися пункти, з яких у майбутньому мало складатися прохання парафіян про будівництво чи відновлення церкви.11
Святитель Павло не хотів миритися з безконтрольним збором пожертв на будівництво храмів. Ще попередні архієреї для нього ввели «шнурові книги» у яких ті, що збирали кошти, повинні були суворо стежити за записами пожертв. Дозволи на подібні збори видавалися десятками й сотнями безперешкодно. Митрополит Павло обмежив кількість шнурових книг і видавав їх переважно тоді, коли будувалася камінна церква, яка вимагала більших затрат.12 Загалом, на думку дослідників, саме Павло Конюшкевич у 1760-их роках зумів різко покращити діловодство та звітність у своєму відомстві, які за інших архієреїв велися недбало.13 Завдяки порядку й контролю за час перебування святителя Павла на Тобольській кафедрі збудовано багато храмів, особливо камінних.14
Перш за все, було відновлено Богоявленську Церкву, яка за місяць до приїзду святителя згоріла разом із дерев’яною Захаріївською церквою. На місці Захаріївської 11 червня 1759 р. митрополит Павло заклав камінну двохповерхову церкву: згори — на честь Воскресіння Христового, внизу — святих Захарії і Єлизавети, з приділом св. Димитрія Ростовського. 1 квітня 1761 р. в Тобольську було освячено камінну Христовоздвиженську церкву. Того ж року, 12 вересня освячена в нижньому поверсі камінна церква на честь Покрови Пресвятої Богородиці. 28 квітня 1762 р. в Тобольському жіночому монастирі архієрей освятив літню церкву Різдва Богородиці, а при Благовіщенській церкві того ж року завершилося будівництво камінної дзвіниці. У Стрітенській церкві 27 жовтня 1762 р. освячено приділ на ім’я св. мучениці Параскеви П’ятниці.
У Знаменському монастирі українець Михайло (Міткевич) 1767 р. завершив будівництво камінної дзвіниці й камінної двохповерхової церкви: внизу — на ім’я свят. Миколая, згори — на честь Казанської ікони Божої Матері.
У місті Березові 1765 р. на місці згорілого храму на честь Різдва Богородиці за грамотою митрополита Павла побудовано камінну церкву. У м. Ялуторовську в 60-ті роки ХVІІІ століття, згідно грамоти митрополита Павла, зведено двохповерхову камінну Стрітенську церкву. У Тюмені 1765 р. закладено камінну Успенську церкву. На місці Спаської дерев’яної церкви, яка згоріла 4 червня 1766 р., 1769 р. побудовано камінну.
У місті Тарі святитель освятив першу камінну двохповерхову Спаську церкву. У м. Красноярську близько 1759 р. розпочато будівництво камінної соборної Троїцької церкви. Також чимало збудовано й освячено преосвященним Павлом церков і в інших провінційних містах і селах.
Дбаючи про семінарію, яка мала випускати потрібну кількість священнослужителів, будуючи храми, наводячи порядок в єпархії, тобто, створюючи базис, митрополит Павло постійно й безпосередньо займався місіонерськими справами. Для ознайомлення зі станом місіонерської справи в єпархії святитель Тобольський здійснював особисті візити в різні місця, незважаючи на труднощі, пов’язані з подорожами по Сибіру. Так, приміром, у лютому-березні 1762 р. він відвідав «верховні міста та інші визначні місця Тобольської єпархії» (за маршрутом з Тобольська через Тюмень та Турінськ до Верхотур’я). Його супроводжував численний почет, який складався з архімандритів, священиків, дияконів та хористів, котрі, очевидно, були необхідні для здійснення архієрейського богослужіння в різних місцях єпархії.15
Неподалік кафедри митрополита Павла було Джунгарське (Калмицьке) ханство, яке межувало з Південним Сибіром річками Іртишом й Ішімом. У першу чергу сюди звернув ревний архіпастир слово євангельської проповіді. З довірою поставилися калмики до проповіді святителя Павла й охоче хрестилися. Коли китайська армія в 1757—1758 рр. зруйнувала Джунгарське ханство, дехто з джунгарців і їхніх тайшів (князів) рятувались у російських фортецях: Семипалатинську, Усть-Каменогорську, Ямишевську й ін., а також у містах Тарі й Тобольську. Там приймали вони російське підданство та православну віру. Серед них був сам Контайша (хан) Амурсана з жінкою Бетей і сином Пунцуком, котрі, прибувши до Тобольська, жили в заміському архієрейському будинку.16
З метою пожвавлення місіонерської справи у Тобольській єпархії, святитель Павло 1764 р. запровадив у Тобольську посади двох спеціальних місіонерів для проповіді християнства серед іновірців-ідолопоклонників і для утвердження новонавернених з язичництва в істинах православної віри. На затверджені тоді посади місіонерів святитель подбав призначити найосвіченіших осіб із середовища духовенства Тобольської єпархії.
Інструкції, правила й поради, з якими звертався святитель Павло до різних духовних осіб своєї єпархії з цього приводу, ясно свідчать про глибоку любов та істинно апостольське піклування його про нещасних людей, що не знали правдивого Бога. Протопопів «заказчиків», а через них і загалом усіх священиків Тобольської єпархії святитель Павло настійливо переконував ставитися з любов’ю та поблажливістю до ще нехрещених, заохочувати їх до прийняття таїнства хрещення, охороняти й захищати їх від лиха. Так, приміром, в інструкції протопопам — Дем’янському й Норимському святитель Павло наказував: «Поганським народам проповідувати Слово Боже та приводити їх до пізнання Єдиного Триіпостасного Бога, у Трійці Святій славимого і поклоняємого від усього творіння Отця і Сина і Святого Духа. Навертати їх пристойним чином, беручи за приклад апостолів: добровільно, з ласкою і без озлоблення. Тих із них, котрі добровільно бажатимуть хрещення, просвіщати святим хрещенням, не обтяжуючи їх на перших порах. Навчати їх найкоротших і найнеобхідніших молитов та спостерігати за їхніми нахилами й намірами. А вже згодом, коли охрестяться, подати їм достатньо настанов, навчити молитов і смиренно розповідати про віру, надію й любов до Бога та ближнього. Запроваджувати в них християнські звичаї привітно й ласкаво. Щоб через це в інших розбудити бажання до святого хрещення, а образ і озлоблення не допускати».17
Великих зусиль доклав митрополит Павло для покращення внутрішньої організації місії. Уряд не піклувався про місію, більше заважав їй. Місцеві кошти після секуляризації були мізерні. Місіонерська справа вимагала не тільки особливого піклування з боку єпархіального архієрея, а й штату його помічників. Відсутність місіонерів ускладнювала справу просвіти іновірців; а тут, як писав митрополит Антоній Стаховський (1721—1740) роботи вистачило б не на 70, а на 700 проповідників.18
Як уже говорилося, святитель Павло домігся від Святійшого Синоду дозволу лише на дві посади спеціальних проповідників місіонерів. Хоча їм і було призначено зарплату, але про регулярне надходження її не подбали. Коли Святійший Синод 19 травня 1768 р. вимагав відомості з єпархії про проповідників серед іновірців, то з Тобольської єпархії повідомили, що призначена проповідникам-місіонерам: протоієрею Афанасію Туясову та протоієрею Олексію Михайлівському зарплата з кінця 1766 р. в Тобольськ не надходила.