Николо-Корельский монастырь был возобновлен полвека спустя на средства знаменитой новгородки Марфы Посадницы. К тому времени Беломорье уже освящалось молитвами иноков новой обители на Соловецких островах. Слава одного из его зачинателей, Зосимы Соловецкого, была так велика, что «многие из окрестных дикарей сами приходили к нему, принимали святое крещение и даже постригались в монашество».
Ну а неофициальные боевые действия на порубежье продолжались. К примеру, русские не забывали, что Каянская земля по праву принадлежит им, и ходили туда за данью. Итогом этих походов были пепелища ограбленных финских поселений, с русской точки зрения возникавших там незаконно. Шведы с норвежцами ответно посылали свои судовые рати на Белое море. Но таких кровавых разгромов, как в 1419 году, им уже не давали совершать.
Московская Русь, включив в свой состав новгородские владения, заполучила в наследство и эту проблему. Во время русско-шведской войны конца XV века Иван III отправил большую рать на Каяно-море. Войско, набранное в северных русских землях, переплыло Белое море и реками ушло к Ботническому заливу, повоевало там карельских жителей «семи рек» и привело их под присягу московскому князю. Однако присоединить территорию всё же не удалось – слишком труднопроходимые леса и болота отделяли ее от русской Карелии. Разбойная война на пограничье вскоре возобновилась.
Наверное, есть какой-то символизм в том, что основателем самого северного русского монастыря-форпоста на Мурмане стал непосредственный участник этой войны. Трифон Печенгский (мирское имя, предположительно, Митрофан) был предводителем одного из отрядов то ли сборщиков дани, то ли охотников за добычей, что периодически наведывались в Каянские края и более северную норвежскую Лапландию. По собственному его рассказу (записанному позднее голландским купцом Симоном ван Салингеном), он «был грозным для врагов воином, много народу ограбил и разорил на границе и много крови пролил, в чем раскаялся и о чем горько сожалел».
В преданиях саамов сохранилась «романтическая» история о том, как жестокого атамана разбойников Трифона сопровождала в походах его возлюбленная Елена. И как однажды он в припадке гнева нечаянно ее убил.
Сильнейший порыв раскаяния погнал его на край земли. Около 1514 года Трифон в одиночестве ушел далеко на север, на мурманское побережье океана. Через пять лет горьких скитаний он встретил другого пустынника, монаха Феодорита. Судьба свела двух будущих просветителей Русской Лапландии, и с этих пор они, хотя и расставались на годы, никогда не теряли друг друга из вида.
Феодорит Кольский пришел на Мурман, имея вдохновенный замысел приобщать к христианству лопарей. Этот народ издревле стяжал славу страшных колдунов. Норманны называли их «языческими чудовищами». Темное лопское колдовство вызывало опасения у окрестных народов, в том числе и у русских. Шведы и финны выведывали у лопарей секреты их «боевой магии». Даже Шекспир был наслышан о них: «Не сомневаюсь я, / Что это все проделки чародейства, / Что много здесь лапландских колдунов» («Комедия ошибок», перевод П. Вейнберга). Особенно могучими чародеями, приручившими бесовскую силу, слыли кольские лопари. Так что проповедь христианства в этих краях была связана не просто со смертельной опасностью (могли убить), но и с риском погубить собственную душу. Этот тяжелый труд был по плечу лишь настоящим святым, которые могли без вреда для себя побороться с бесовскими кознями и мороками.
Трифон многому научился от опытного в духовных делах Феодорита – молитве, православной аскетике. Перенял у него миссионерское горение духа. О плодах их деятельности рассказывают летописи: в 1526 и 1532 годах к великому князю Василию III и новгородскому архиепископу Макарию приходили послы от лопарей с просьбами прислать им священников, чтобы крестить уверовавших, освятить церкви и начать богослужение. Храмы были поставлены в южной части Кольского полуострова – в Кандалакше и на севере – в вершине Кольской губы, на месте будущей Колы.
Вскоре оба подвижника сами отправились в Новгород. К обширной Новгородской епархии относились тогда все северные земли до океана. Феодорит и Трифон поведали владыке о своих трудах и нуждах новокрещеных лопарей. Макария, будущего митрополита всея Руси, просветителя, радетеля русской культуры и государственности, их рассказ обрадовал. Наверное, после он сам завел речь о необходимости утверждения Руси в малолюдном лопском краю, наполнения его христианским духом, устроения там центров русского присутствия – монастырей. Из двух кольских подвижников, может быть, глубже понимал эти заботы Макария именно Трифон. На опыте собственной боевой молодости он убедился, насколько острой была нужда в присутствии государства на карельских и лопских землях, где царила разбойная воля пришельцев со всех сторон: кто сильнее, тот и взял. И насколько зыбки там заявляемые права на ту или иную территорию.