Границы Норвегии и Новгорода были определены уже в X веке, но в 1251 году их закрепил договор, который заключили послы, отправленные Александром Невским в столицу Норвегии Нидар (теперешний Тронхейм).

«Прибыли с востока, из Гердарики, послы Александра, конунга Холмгарда», — сообщила об этом событии сага. Добрались они до западного побережья Норвегии через Балтийское море и Данию. Это были первые русские на западном побережье Скандинавского полуострова. Можно считать их первооткрывателями. Мир был заключен, но на севере соперничество продолжалось. В 1316 и 1323 годах новгородцы совершили военные походы в Норвегию, проникнув южнее Финмарка, самой северной провинции Норвегии.

Для противостояния этим вторжениям норвежцы построили на острове у западного берега Варангер-фиорда крепость Вардэгус. Но плавания новгородцев вдоль берегов Баренцева моря продолжались, так же как и их регулярные посещения берегов Белого моря. Два этих достаточно удаленных друг от друга региона исторически оказались близкими. Да и море, их соединявшее, называлось то Варяжским, то Мурманским, то Печорским.

Связующим центром был Новгород, в середине XII века торговавший со скандинавским городом Висби на острове Готланд и с городами Ганзейского торгового союза. «Ушкуйниками» новгородцев называли потому, что они добирались до Северной Двины и Белого моря на своих лодках — «ушкуях». И ничуть не менее норманнов-викингов грабили они местное лопарское население, оттесняя его от моря. В 1342 году новгородский боярин Лука Варфоломеев построил на Северной Двине и неподалеку от позже появившихся Холмогор крепость Орлец, ставший центром колонизации в Беломорье.

Со временем у новгородцев появились сильные конкуренты в московском княжестве, тоже претендовавшие на дань с пушного приморского края. Заволочьем называли его и новгородцы, и москвичи, потому что путь туда был связан с перетаскиванием лодок из одной реки в другую волоками. Всего 55 лет Орлец новгородский безраздельно главенствовал над Поморьем. Но однажды московско-владимирский-вятский князь Василий Дмитриевич, воспользовавшись предательством воеводы, захватил двинскую землю и посадил в Орлеце своего наместника. Новгородцы не смирились и послали свое ополчение, которое разгромило московское войско и, преследуя его, даже вторглось в пределы московского княжества. Власть Новгорода над Поморьем сохранялась еще почти столетие до тех пор, пока в 1478 году после длительной борьбы самостоятельность Великого Новгорода не была уничтожена. Поморье было присоединено к Москве, стало ее колонией.

Еще через полвека продолжилось освоение мурманского побережья Кольского полуострова, активно посещавшегося новгородцами, основавшими еще в середине XIII века селение Кола. Теперь там появился богатый монастырь в Печенге (в 1530—1540 годах). Монахи торговали рыбой и солью, строили морские суда, всячески притесняли «нехристей» — лопарей. Со стадами оленей им пришлось откочевать в горную часть полуострова.

«Русским Отаром» можно назвать Григория Истому, московского дьяка, отправленного в 1496 году великим князем Иваном III послом в Данию. Если Отар был первым, кто совершил путешествие вокруг Скандинавского полуострова в Белое море, то Истома тот же путь проделал в обратном направлении спустя тысячелетие.

Тогда шла война со шведами, и обычный путь через Новгород был невозможен. Решено было отправиться вокруг Скандинавского полуострова северным путем. Четыре парусных лодки с посольством вышли из Архангельска и прошли вдоль берега Кольского полуострова.

Рассказ Истомы изложил в своих «Записках о московских делах» австрийский посол в Москве Сигизмунд Герберштейн. Для русских новым был путь к западу от полуострова Рыбачьего. Далеко выступающий в море мыс пришлось пересекать по суше. «…Мы перенесли свои суда и груз через перешеек в полмили шириной, — рассказывал Григорий Истома, — потом мы проплыли в землю дикой лопи… Здесь, оставив лодьи, мы дальнейший путь проделали по суше на санях».

Лопарская упряжка оленей доставила московское посольство в город Берген, откуда до границ Дании добрались в карете, запряженной лошадьми.

В том же году, что и Григорий Истома, два воеводы, князья Петр и Иван Ушатые, как сказано в летописи, «…ходили с Северной Двины, морем-океаном да через Мурманский нос». Дальше они от Варангер-фиорда поднялись по реке Патсиоки до озера Инари, а потом по малым рекам и частично волоком спустились к Ботническому заливу. В летописи сказано, что жившие в этом месте «били челом за великого князя».

Тем временем на востоке Поморья началось движение за Урал, в Сибирь, где новгородцы проложили волоки еще четыре столетия назад. В летописи рассказывается о том, что еще в 1032 году воевода Улеба прошел через некие Железные ворота, по-видимому, через горное ущелье, а оно могло быть только на Урале. И в последующие годы новгородцы ходили «в Печору и Югру» собирать дань с самояди. Не раз приходилось жестоко подавлять сопротивление аборигенов. Последний поход новгородцев в югорскую землю был особенно грандиозным: в нем участвовало три тысячи человек.

Идя «встречь солнцу», беломорские поморы, а за ними новгородские ушкуйники первыми из европейцев перевалили естественную границу двух частей света — перешли из Европы в Азию. Они основали здесь торговый город, который стал первой базой для дальнейшего продвижения в азиатские просторы — на восток, к Тихому океану.

На этом пути вставал Уральский хребет. Камень, как называли его в летописи: «Камень превысочайший зело яко досязати иным холмам до облак небесных… из сего же камня реки многие истекоша… пространные и прекрасные зело, в них же воды сладчайшие и рыбы различные множество».

Земли за Уралом и Обской губой населяла самоядь — ненецкое племя «малканзеи» (так оно названо в новгородских летописях). Отсюда и название Мангазея, что на языке зырян значит «земля около моря». Имелся в виду большой залив Карского моря — Обская губа, от которого ответвлялся залив поменьше — Тазовская губа. Город возник при впадении в Таз маленькой реки Мангазейки. Здесь было царство пушнины. За ней-то и ходили люди «из-за Камня».

В 1597 году помор из Усть-Цильмы на Печоре Юрий Долгушин «со товарищи» проведал дорогу на реку Таз. От Печоры он пришел на Обь, в Усть-Надым, где перезимовал, и на следующее лето вышел к стране Мангазейской. В следующем году из Тобольска пошел отряд стрельцов во главе с думным дьяком Федором Дьяковым — посланы они были Яковом и Григорием Строгановыми по указу царя Федора Ивановича. В Мангазее уже были поморы, собирали ясак — себе, а не государю, поэтому Дьяков посчитал их «ворами».

В августе 1600 года в Обскую губу вошли суда с большим отрядом стрельцов во главе с князем Мироном Шаховским. Разыгравшийся шторм выбросил их на берег. Люди Шаховского пошли было через тундру, но их встретили «малканзеи», вступившие в бой. Несколько стрельцов были убиты, а Шаховской ранен. Больше ничего об этом первом военном походе в Мангазею неизвестно.

Второй поход на следующий год возглавил князь Василий Мосальский и боярин Савлук Пушкин. Стрельцов и казаков было вдвое больше, и вооружены они пищалями. На сей раз победа была на их стороне.

О строительстве города Мангазеи издал указ Лжедмитрий I. То были времена великой смуты. Страшный голод поразил Россию в 1601—1603 годах. Тысячи беглых крестьян хлынули на север. В апреле 1605 г. умер Борис Годунов. В 1606 году воевода Давыд Жеребцов и письменный голова Курдюк Давыдов прибыли на реку Таз, где уже стоял острог. А в дальнейшем есть такая запись, сделанная в соборной церкви Троицы: «…зарублен город на месте острога Мангазеи на Тазу реке, три церкви, гостиный двор и „государевы житницы“ — склады». Поскольку строительство шло на вечной мерзлоте, фундаменты домов возводились на слое замороженной щепы, прикрытой сверху листами бересты, чтобы в замороженный слой не проходила талая вода. А домов в городе было не меньше пятисот. Мангазея принимала купцов даже из стран Западной Европы. Из Обской губы и Тазовской приходили грузовые кочи водоизмещением до 90 тонн. И в год их прибывало по несколько тысяч. И иностранцы прибывали сначала в Пустозерск на Печоре, а потом пересекали Ямал, где между реками Леуткой и Зеленой был волок недели на три ходу. Столько же надо было плыть до Оби на веслах по реке Зеленой, а там до Мангазеи — еще неделя ходу. Трудный путь, но он был все-таки короче, чем «южный-чрезкаменный», то есть через Средний Урал. Но властям в Тобольске этот путь был более выгоден, и тобольский губернатор князь Иван Куракин сумел убедить Михаила Федоровича, избранного на царство, в необходимости пресечь интерес иностранцев к мангазейской пушнине и закрыть «мангазейский морской ход». Москва согласилась с этим предложением.