Вскоре норвежцы исследовали фьорды и острова вдоль западного побережья. Береговая линия летом чаще всего была свободна ото льда благодаря теплому Западно-Гренландскому течению, которое огибает западное побережье Гренландии и впадает в море Баффина. Благоприятное течение несло корабли поселенцев к островам и фьордам вокруг залива Диско. Эту местность они назвали Норорсетой; здешние воды изобиловали треской, тюленями и моржами. В Норорсете находились важные охотничьи угодья, где колонисты заготавливали продовольствие на зиму и добывали предметы торговли, в том числе бивни нарвалов и моржей, которые ценились очень высоко. Многие годы гренландские церкви выплачивали часть десятины норвежской епархии моржовой костью.
Гренландцы, плававшие в Норорсету, должны были быстро узнать о землях на западе – хотя бы потому, что именно туда несли их преобладающие течения в районе северных охотничьих угодий. Пролив Дейвиса в самом узком месте имеет ширину чуть более 325 км. Даже если отплыть не очень далеко от берегов Гренландии, при хорошей видимости можно разглядеть высокие горы на Баффиновой Земле. Скандинавы открыли Северную Америку благодаря неизбежному стечению обстоятельств: они заметили арктические острова и материк задолго до того, как ступили на западное побережье. Они прибыли в Норорсету в то время, когда летняя ледовая обстановка была менее сложной, чем в позднейшие века. Это позволило им обратить себе на пользу течения вдоль американского берега пролива.
Западно-Гренландское течение достигает моря Баффина и центральной части Норорсеты, где уступает место более холодным южным течениям. Холодные воды текут на юг вдоль Баффиновой Земли, полуострова Лабрадор и восточного побережья Ньюфаундленда. Такая схема циркуляции вод влияет на образование льда. На побережье Баффиновой Земли и Лабрадора ледяной покров толще, а море в течение года дольше сковано льдом, в то время как у берегов Гренландии морские льды формируются позднее и тают раньше. На восточной стороне пролива Дейвиса часто образуется прибрежная полоса свободной ото льда воды, тянущаяся до Северного полярного круга. Вероятно, средневековый климатический оптимум многие годы обеспечивал легкую летнюю навигацию между Баффиновой Землей и Лабрадором.
И все же первые задокументированные наблюдения были сделаны не во время таких путешествий на север вдоль побережья. Примерно в 985 году молодой купец и судовладелец Бьярни Херьюльфссон, «человек с большим будущим», который мечтал исследовать чужие края, прибыл из Норвегии в Исландию и был потрясен, узнав, что незадолго до этого его отец переселился в Гренландию с Эриком Рыжим. Он решил не разгружать корабль и немедленно отправился в Гренландию, воспользовавшись попутным ветром. Однако вскоре ветер изменился. Несколько дней Бьярни и его спутники плыли в тумане при северном ветре, не имея ни малейшего представления, где находятся. Наконец они увидели пологий лесистый берег, совершенно не похожий на тот, к которому направлялись, «ибо в Гренландии, как говорят, огромные ледники». Бьярни двигался вдоль берега на юг, периодически находя все новые земли. В конце концов сильный юго-западный ветер унес их от побережья. Через четыре дня они в сумерках причалили к мысу, где уже было пришвартовано судно, и таким образом наконец достигли первоначальной цели.
Соотечественники единодушно осуждали осторожного Херьюльфссона за то, что он не высадился на загадочную землю. Лейф Эрикссон, сын Эрика Рыжего, купил корабль Бьярни, собрал команду из 35 человек и отплыл на запад, к Баффиновой Земле. Самому Эрику пришлось остаться дома после того, как он получил травму на пути к судну. Лейф бросил якорь у скалистого, покрытого ледниками берега, а затем отправился на юг, к ровному, густо поросшему деревьями побережью с песчаными пляжами, которое «за его богатства» он назвал Маркланд («земля лесов»). Он причалил к полуострову Лабрадор чуть южнее северной границы леса, неподалеку от залива Гамильтона. Попутный северо-восточный ветер отнес путешественников еще дальше на юг, к устью реки Святого Лаврентия и территории, которую они назвали Винланд («винная земля») – вероятно, из-за обнаруженного там дикого винограда.
Известный археологический памятник Л’Анс-о-Медоуз на самом севере Ньюфаундленда может быть тем самым местом, где Лейф Эрикссон и его команда перезимовали и основали перевалочную базу, на которой выделывали меха и обрабатывали древесину перед отправкой в Гренландию. Археологи Хельге и Анна Стина Ингстад раскопали восемь строений с земляными стенами на террасе, возвышающейся над мелководной бухтой. В поселении имелись мастерская, кузница, а также склады и четыре лодочных сарая из дерна. Норвежцы знали, как выбирать место для зимовки. Л’Анс-о-Медоуз находится на стратегически удобном мысе над проливом Белл-Айл в устье реки Святого Лаврентия. Это место с трех сторон окружено водой, и здесь имеются обширные пастбища. Из Л’Анса, а возможно, и из других поселений, скандинавы странствовали во многих направлениях, но вопрос о том, как далеко они заплывали на юг вдоль побережья материка, до сих пор остается предметом споров.