После некоторого отдыха и приведения судов в порядок Колумб направился через юго-западную оконечность Эспаньолы к Ямайке, обогнул ее по южному и западному берегам, а затем поднялся на северо-запад к южному побережью Кубы. Здесь 21 июля флотилия вышла в полосу северо-восточного ветра, на котором она уже через три дня пересекла 360 миль Карибских вод и вышла к мелким островам около сегодняшнего Гондураса. Это название происходит от испанского «honduras», что означает «глубины» или «глубокие места», которыми отличается северная часть прибрежных вод будущей провинции и страны. Около одного такого места каравеллы встали на стоянку, а уже скоро испанцы познакомились с первыми местными жителями незнакомых земель, выплывшими к ним навстречу на огромном каноэ и направлявшимися куда-то на материк с массой местных товаров, но золота и чего-либо другого привлекательного для пришельцев у них не оказалось. Здесь индейцы говорили на неизвестном для переводчиков-таино языке, так что объясняться снова пришлось жестами, а в качестве гида и будущего переводчика с языком местных жителей хикаке испанцы силой захватили одного из пассажиров каноэ.
После этого Колумб направил каравеллы к берегу континента и, не теряя времени, приступил к поиску пролива. Поскольку в этой его части зеленая полоса земли тянулась далеко с запада на восток, а встречное течение и крепкие ветры шли с востока, он решил начать обследование со свежими силами именно в этом направлении, чтобы с меньшими трудностями потом возвращаться обратно. Погода быстро испортилась, и на протяжении почти целого месяца, борясь с непрекращающимися грозовыми ливнями, возросшими встречными ветрами и течением, каравеллы с огромным трудом буквально пробивались вперед в почти непрерывную штормовую погоду. В ходе этой затянувшейся борьбы с неумолимой стихией суда теряли якоря, канаты, лодки, паруса и запасы, а люди до того уставали, что утрачивали надежду на выход из мучивших их испытаний живыми. Сам Адмирал в это время болел настолько серьезно, что, по его собственному признанию, несколько раз оказывался на пороге смерти. Его особенно беспокоили страдания 12-летнего сына Диего, который, несмотря на свой совсем юный возраст, в этих труднейших условиях проявлял немало мужества, подавая пример даже старым морским волкам, что служило отцу некоторым утешением. Чтобы постоянно следить за ходом этого мучительного плавания, Колумб приказал смастерить для него на корме маленькую конуру, из которой он отдавал необходимые команды. Он не хотел терять время и припасы на ожидание изменения погоды или уходить далеко от берега, чтобы не пропустить искомого пролива. В результате упорным парусникам удавалось проходить в среднем всего около шести жалких миль в день.
Наконец, на 29-й день безумно изматывающего пути каравеллы подошли к сильно выходившему в море мысу, где широкий песчаный берег довольно круто менял направление на юг, а ветер становился их боковым союзником. Со вздохом огромного облегчения и благодарности всевышнему Колумб назвал эту оконечность мысом «Спасибо Богу» («Грасиас а Диос»). Теперь испанцы были у территории будущей Никарагуа. Продвинувшись на 120 миль к югу, Адмирал обнаружил устье реки, к которой он решил направить плоскодонную лодку для сбора дров и пополнения запасов воды. При возвращении лодка перевернулась при преодолении опасной песчаной косы, потеряв двух матросов. Продолжая путь на юг, флотилия прошла ночью мимо устья реки, которая позже получила название Сан-Хуан-дель-Норте. Эта река вытекала из большого озера Никарагуа, западный берег которого находился всего в 15 милях от Тихого океана. Не заметив тогда эту реку, Колумб лишился столь близкого и чрезвычайно важного нового открытия. Озеро Никарагуа в своем названии повторяло имя местного индейского вождя и впоследствии дало название всей будущей испанской провинции и образовавшейся на ней стране.
К югу от впадения реки Сан-Хуан в Карибское море путешественники повстречались с приветливыми хозяевами этих мест — индейцами племени таламаика, которые не могли предложить пришельцам ничего интересного из своих товаров, но получили от них приготовленные для таких случаев яркие и звонкие безделушки. Здесь для обследования прибрежных районов Колумб отправил целую экспедицию, которая при возвращении через несколько дней сообщила о большом природном изобилии этого края и принесла с собой его различные образцы, в том числе незнакомую по породе мартышку, американскую свинью пекари и других, которые служили веселым развлечением для экипажей. Несколько позже путешественники, к своей великой радости, обнаружили на побережье индейцев, носивших в качестве украшений крупные диски из чистого золота, которые с удовольствием их обменивали на обычный испанский товар. Отражая такие богатые впечатления от этой земли, испанцы впоследствии назвали ее Коста-Рика, что по-испански означает «богатый берег».
В течение почти двух недель Адмирал продолжал безуспешные поиски пролива и одновременно собирал золото. Исследование очень затруднялось отсутствием переводчика при выяснении у местных жителей сведений о местности, а объяснения на языке жестов нередко приводили к непониманию или неправильному восприятию ответов на вопросы о проливе, что вызывало потерю времени и усилий. Колумб начинает приходить к заключению, что в этих краях пролива не существует, и сосредоточивается на сборе золота и обнаружении удобного места для торговой фактории. После 10 дней пребывания в широкой лагуне Чирики флотилия выплывает в залив Москитос, где берег снова вытягивается в восточном направлении, и проходит под попутным западным ветром свыше 120 миль до залива Лимон. Здесь уже начиналась территория будущей Панамы, получившей свое название по имени рыбацкой деревни индейцев, которую потом откроет Бальбоа у места сегодняшней одноименной столицы страны. Однако из-за отсутствия удобной стоянки и враждебного поведения со стороны местных индейцев, Адмирал продолжает путь до великолепной гавани, которую он назвал Пуэрто-Бельо («Прекрасный Порт»).
В этом месте испанцы пробыли несколько дней, пополняя запасы и собирая у индейцев хлопок, а следующую остановку сделали в крохотной, но уютной гавани Пуэрто-дель-Ретрете, жители которой встретили пришельцев настолько враждебно, что последним пришлось применить огнестрельное оружие для отпора нападавших хозяев. Погода по-прежнему так продолжала мешать дальнейшему продвижению, что Колумб принимает решение вернуться в Пуэрто-Бельо, где рассчитывал получить у индейцев дополнительные золотые украшения. Когда каравеллы достигли этой гавани, ветер и течение вдруг снова переменились в обратную сторону. Как убедились на своем горьком опыте путешественники, в этих водах и ветер и течение меняются почти одновременно и меняются довольно часто, что превращает плавание в бесконечное мотание с запада на восток и обратно. Беспомощные парусники в течение целого месяца носило то вперед, то назад, не позволяя им продвигаться ни на запад, ни на восток. Навигацию еще больше усугубляли непрекращающиеся страшные ливни с громом и молниями, заставившие Адмирала сравнить заливавшие суда потоки воды с новым потопом. Люди были совершенно измотаны выпавшими на них новыми невыносимыми испытаниями, которые усугублялись постоянно сокращавшимися рационами питания. В ходе наступивших затем двух дней затишья им удалось подкрепиться мясом нескольких выловленных акул и привести каравеллы в удобную гавань, названную Кристобаль, в зоне сегодняшнего Панамского канала. Здесь обессиленные и голодающие экипажи встретили Рождество и новый, 1503 год.
После новогодней передышки Колумб продолжил обратный путь на запад вдоль негостеприимного берега Панамы в поисках места для основания фактории и 6 января обнаружил устье реки, которую в связи с выпавшим на тот день праздником Богоявления назвал Белен, то есть Вифлеем. Несколько дней спустя немного далее на запад корабельные лодки во главе с Бартоломео Колумбом открыли еще одну реку под названием Верагуа, по которой они поднялись вверх по течению, где обнаружили индейское поселение и наличие у его жителей золота. Вернувшись сюда через несколько дней, группа Бартоломео с помощью только своих ножей могла набрать в земле неожиданно много кусочков золота. Эта находка определила решение Адмирала основать на холме в устье реки Белен торговый пост с названием Санта-Мария-де-Белен, где он собрался оставить группу людей во главе с Бартоломео, а самому вернуться в Испанию за провиантом и колонистами.
Исходя из этого, все каравеллы благодаря сильным дождям и возникшему наводнению удалось ввести через песчаную косу в устье реки, где началось строительство укрепленного форта. Надо сказать, что выбранное Колумбом место торгового поста было чрезвычайно неудачным, так как весь окружавший его район подвергался огромному количеству осадков и сильным наводнениям, не говоря уже о невероятном количестве москитов и свирепствующей здесь малярии. Кроме того, европейцы не смогли сохранить хорошие отношения с хозяевами края. Пока продолжались строительные работы, испанцы небольшими группами стали скрытно проникать в индейское поселение золотоносного района, где касике Кибиан и его племя первоначально встретили пришельцев довольно дружелюбно, и силой оружия отнимать золото и женщин. Возмущенные таким поведением непрошеных соседей, индейцы стали готовиться к ответному удару по форту, но испанцам удалось узнать об этих планах и заблаговременно поймать в засаде Кибиана и около 30 его соплеменников.
Однако касике и большинству индейцев вскоре удалось бежать из плена и возглавить нападение на форт. Оно произошло как раз в то время, когда испанцы только закончили перетаскивание трех из четырех каравелл перед их отплытием в Испанию через обмелевшую песчаную косу речного русла в море и прощались с остающимися вместе с одним из парусников соотечественниками. Первую атаку индейцев 20 поселенцам с их овчаркой удалось отбить. Но отошедшие от форта туземцы обнаружили лодку испанцев во главе с капитаном флагмана Диего Тристаном, который возвращался по реке с последними пополнениями запасов воды к уходившим каравеллам Кибиан и его люди напали на лодку и убили всех, кто в ней находился, за исключением одного спасшегося в суматохе человека.