В середине XIII века новгородцы основали на северном побережье Кольского полуострова селение Кола, а через семь десятилетий появился богатый монастырь в Печенге, занимавшийся торговлей рыбой и солью и даже строительством небольших морских судов. Московский дьяк Григорий Истома, отправленный великим князем Иваном III послом в Данию, первым совершил путешествие вокруг северных берегов Скандинавского полуострова, двигаясь с востока на запад. «Мы перенесли свои суда и груз через перешеек в пол мили шириной, потом проплыли в землю дикой лопи... Здесь, оставив лодьи, мы дальнейший путь проделали по суше, на санях». Так Истома рассказывал о своём путешествии австрийскому послу в Москве Сигизмунду Герберштейну. Лопари на оленьей упряжке доставили московского посла в город Берген, откуда он отправился к королевской столице на лошадях.

Движение на восток новгородцы начали в то же время. Медленно, но неуклонно продвигались они через леса и болота в северо-восточном направлении. В 1032 году новгородский воевода Улеба прошёл через некие Железные Ворота, очевидно, расположенные на Урале. Новгородец Гюрята Рогович рассказал в 1096 году летописцу Нестору, что он послал некоего отрока в Печору за сбором дани с местных жителей, и тот прошёл дальше, в землю Югорскую, где ему рассказали о горах, доходящих до моря. «Им же высота ако до небес...» — сообщает «Повесть временных лет». — Есть же путь до тех гор непроходим пропастями и лесом». Несомненно, речь здесь идёт об Урале. Значит, уже в конце XI в. новгородцы знали о нём.

В 1193 году воевода Ядрей, возглавивший поход отчаянных новгородцев-ушкуйников в Северное Зауралье, взял дань с живущего в тундре народа «самоядь» изделиями из моржовой и мамонтовой кости. В 1342 году новгородец Лука Варфоломеев построил на Северной Двине крепость Орлец. Больше полувека Орлец безраздельно властвовал над северным приморским краем, который они называли Заволочьем (потому что путь пролегал через волоки между верховьями рек).

Первое определённое сообщение о том, что новгородцы достигли берега Северного Ледовитого океана и перешли на восточный склон Уральских гор, появилось в новгородской летописи в 1364 году: «...приехаша дети болярские и малые люди и воеводы Александр Авакумович, Степан Ляпа, воевавшие по Обе реке до моря...» А через 15 лет поселился за Уралом, на реке Вычегде, проповедник Стефан Храп, получивший сан «епископа пермского». Он крестил коми и пермяков, а в 1395 году составил первое описание Северной Двины и многих притоков Камы, «обходящей всю землю пермскую». Но постепенно, как и на западе, стало вытеснять новгородскую вольницу более сильное Московское княжество.

Великий князь московский прислал в Орлец своего наместника. Новгородцы, чтобы прогнать его, собрали ополчение, захватили Орлец, восстановили свою власть. Потом борьба продолжалась ещё целое столетие, пока в 1478 году Иваном Грозным не была окончательно уничтожена самостоятельность Великого Новгорода.

Потом наступил этап завоевания Сибири Ермаком (войском под предводительством казачьего атамана Ермолая Аленина, прозванного Ермаком, что означает «артельный котёл»). Шестьсот казаков на тридцати стругах и нескольких маленьких лодках прошли под парусами вверх по стиснутой крутыми берегами порожистой реке Чусовой, впадающей в Каму, перешли волоком Средний Урал и на реке Туре одержали первую победу над войском татарского хана Кучума. Однако полный разгром хана произошёл много позже, когда уже не было Ермака, погибшего августовской ночью 1585 года. 20 августа 1598 года отряд воеводы Андрея Воейкова в битве близ устья впадающей в Обь реки Берды завершил противостояние с Кучумовым ханством.