Самое раннее упоминание о северных плаваниях новгородцев имеется в Софийской летописи, где говорится, что в 1032 году новгородский посадник Улеб ходил к «Железным воротам» (возможно, имеется в виду пролив Карские ворота). Известен также рассказ летописца Нестора о посылке в 1096 году новгородским боярином Гюрятой Роговичем своих дружинников за данью в Печорский край и на Северный Урал. Рассказ изложен летописцем от лица самого Гюряты Роговича: «Послал я отрока своего в Печору, к людям, которые дань дают Новгороду. И пришел отрок мой к ним, а оттуда пошел в землю Югорскую. Югра же – это люди, а язык их непонятен, и соседят они с самоядью в северных странах. Югра же сказала отроку моему: «Дивное мы нашли чудо, о котором не слыхали раньше, а началось это еще три года назад; есть горы, заходят они к заливу морскому, высота у них как до неба, и в горах тех стоит клик великий и говор, и секут гору, стремясь высечься из нее; и в горе той просечено оконце малое, и оттуда говорят, но не понять языка их, но показывают на железо и машут руками, прося железа; и если кто даст им нож ли или секиру, они взамен дают меха. Путь же до тех гор непроходим из-за пропастей, снега и леса, потому и не всегда доходим до них; идет он и дальше на север».
Сейчас трудно понять, что за таинстенный народ, проживающий внутри горы (может быть, в пещере?) обнаружили югорцы (по-современному – обские угры, то есть манси или ханты). Вообще в те времена и на русском севере, и в Сибири ходили легенды о неких подземных жителях, которые раньше жили на поверхности земли, но ушли под землю перед лицом каких-то грядущих угроз. На Руси этих подземных жителей называли «чудью белоглазой», а народы Сибири (те же ханты и манси, например – сабирами, савирами, сибирами). Похожие легенды есть и у народов Алтая, и у сибирских (барабинских) татар.
Достоверные сведения о приключениях мореходов Великого Новгорода содержит памятник древнерусской литературы «Послание» Василия Новгородского. По словам писателя-историка С.Н. Маркова, архиепископ Новгородский Василий, «старчище-пилигримище», известный ранее в миру под именем и прозвищем Григория Калики, строил в Новгороде каменные стены, собственными руками чинил мост через Волхов. Он в своё время побывал в Царьграде-Константинополе. Перу архиепископа Василия принадлежит «беседа» о Царьграде, о его достопримечательностях и памятниках прошлого, составленная около 1323 года. В 1347 году Василий закончил одно из своих посланий. В нем описывались дальние морские путешествия новгородцев. «…Много детей моих новгородцев видоки тому: на дышющем море червь не усыпающий, и скрежет зубный, и река смоляная Могр», – писал Василий. Из этих слов явствует, что мореходы, плававшие по «дышющему морю», были современниками Василия. Он лично общался с ними и слышал изустные рассказы об опасностях и муках, которые и «ныне суть на Западе», как выражался он в своем «Послании».
«Где же побывали отважные новгородцы? – пишет С.Н. Марков, – Перед нами открывается необъятная Северная Атлантика. «Червь неусыпающий» – морской слизняк, которым кишат воды Шпицбергена, Ян-Майена и Исландии. «Река смоляная Могр» – мощные потоки чёрной лавы исландских вулканов. И с чем же, как не со «скрежетом зубным», можно сравнить звуки от непрестанного трения льдин друг о друга?
Откуда новгородцы могли начать свое плавание? К тому времени на «дышющем море» уже более столетия существовало новгородское поселение Кола, колыбель древних русских мореходов. В летописях Норвегии и исландских сагах есть подтверждение тому, что в 1316 году русские мореплаватели доходили до Галогаланда. Это северная оконечность Норвегии. Далее расстилался страшный «безбрежный океан, опоясывающий всю землю», как говорил немецкий историк XI века Адам Бременский.
В 1318 году новгородские удальцы снова пошли «за море» и, обогнув Скандинавский полуостров, достигли Ботнического залива. Через два года новгородские «повольники» Лука и Игнат оглядывали со своих судов побережья крайнего севера Норвегии. В 1323 году исландские летописцы занесли в свои свитки свидетельства о том, что русские мореплаватели снова появлялись в Галогаланде. Около 1326 года новгородцы и двиняне опять ходили морем в Скандинавию. Они тогда уже держали в своих руках огромный участок Северного морского пути от Скандинавии до устья Печоры.
В том же послании 1347 года Василий Новгородский рассказал о втором походе отважных новгородских мореплавателей, но уже на Северо-Восток. Он даже называет их имена: Моислав Новгородец и сын его Яков. У них были три судна, снабженные мачтами – «щеглами». «…И всех было их три юмы, и одна из них погибла, много блудив, а две их потом долго носило ветром, и принесло их к высоким горам», – повествует Василий Новгородский.