Впрочем, можно было бы признать самым первым путешественником на Руси апостола Андрея Первозванного, совершившего, как говорится в «Повести временных лет», в начале I века н.э., всего лет через двадцать после казни и воскресения Христа, переход из Западной Европы на земли восточных славян, к реке Волхов, на озёра Ильмень, Нево и Варяжское море (Финский залив). После этого визита возникли города Словенск и Руса...
Конечно, можно всё это считать легендой. Но, если верить летописям, на которые ссылались М.В. Ломоносов и историки В.Н. Татищев и Н.И. Костомаров, то приильменские жители в древнейшие времена доходили до зауральских земель, иначе почему же (опять-таки, если верить летописям) пришла в Словенск «югра мстить» и дважды разорён был город. «Предание о Словенске и Русе, — писал Костомаров, — не лишено исторической действительности».
В Новгородских летописях говорится, что словенско-русские князья доходили до Египта, Греции и Палестины, воевали там. Они путешествовали с воинственными целями, подобно Александру Македонскому и Юлию Цезарю. Но скоро им стало понятно, что торговые отношения более выгодны, чем прямой захват. В XI веке Великий Новгород уже торговал с Западом, собирая в то же время дань с лопарей, кочевавших на больших пространствах от Кольского полуострова до берегов Северного моря. В одной обнаруженной на Кольском полуострове рунической грамоте, относящейся к IX в., содержалось указание на право Холмгарда (Новгорода) собирать дань в стране лопарей практически до границ Норвежского королевства (у Согнефьорда). В пограничной зоне происходили иногда столкновения. В документе, относящемся к 1216 году, перечисляются погибшие в одном из таких сражений, среди них был «терский данник Семён Петролович», собиравший дань на Терском наволоке, как называли тогда Кольский полуостров. В середине XII века Новгород торговал со шведским городом Висби на острове Готланд и с городами Ганзейского торгового союза.
С Норвегией отношения были особыми. Уже в X веке определились границы Норвегии и Новгорода (Холмгарда); их закрепил договор 1251 г., заключённый в норвежской столице Нидаре (теперь Тронхейм) посланцами Александра Невского. Скандинавская сага сообщила об этом так: «Прибыли с востока, из Гардарики (так называли Русь. — В. М.) послы Александра, конунга Холмгарда». Новгородцы добрались до западного побережья Норвегии через Балтийское море и Данию. В следующем столетии, в 1323 и 1326 годах, нарушив договор, новгородцы совершили военные походы на территорию теперешней Норвегии, проникнув южнее провинции Финмарк.
В середине XIII века новгородцы основали на северном побережье Кольского полуострова селение Кола, а через семь десятилетий появился богатый монастырь в Печенге, занимавшийся торговлей рыбой и солью и даже строительством небольших морских судов. Московский дьяк Григорий Истома, отправленный великим князем Иваном III послом в Данию, первым совершил путешествие вокруг северных берегов Скандинавского полуострова, двигаясь с востока на запад. «Мы перенесли свои суда и груз через перешеек в пол мили шириной, потом проплыли в землю дикой лопи... Здесь, оставив лодьи, мы дальнейший путь проделали по суше, на санях». Так Истома рассказывал о своём путешествии австрийскому послу в Москве Сигизмунду Герберштейну. Лопари на оленьей упряжке доставили московского посла в город Берген, откуда он отправился к королевской столице на лошадях.
Движение на восток новгородцы начали в то же время. Медленно, но неуклонно продвигались они через леса и болота в северо-восточном направлении. В 1032 году новгородский воевода Улеба прошёл через некие Железные Ворота, очевидно, расположенные на Урале. Новгородец Гюрята Рогович рассказал в 1096 году летописцу Нестору, что он послал некоего отрока в Печору за сбором дани с местных жителей, и тот прошёл дальше, в землю Югорскую, где ему рассказали о горах, доходящих до моря. «Им же высота ако до небес...» — сообщает «Повесть временных лет». — Есть же путь до тех гор непроходим пропастями и лесом». Несомненно, речь здесь идёт об Урале. Значит, уже в конце XI в. новгородцы знали о нём.
В 1193 году воевода Ядрей, возглавивший поход отчаянных новгородцев-ушкуйников в Северное Зауралье, взял дань с живущего в тундре народа «самоядь» изделиями из моржовой и мамонтовой кости. В 1342 году новгородец Лука Варфоломеев построил на Северной Двине крепость Орлец. Больше полувека Орлец безраздельно властвовал над северным приморским краем, который они называли Заволочьем (потому что путь пролегал через волоки между верховьями рек).