Не доходя форта Навидад, матросы высадились на берег Эспаньолы набрать воды и нашли четыре разложившихся трупа с веревками на шее и на ногах. Один из мертвецов был бородатым, следовательно, европейцем. К форту флотилия подошла ночью 27 ноября и дала сигнал двумя пушечными выстрелами — ответа не последовало.
На рассвете Колумб сам вышел на берег, но не обнаружил ни форта, ни людей — только следы пожарища и трупы. Обстоятельства гибели испанцев выяснить не удалось, по, несомненно, они были виновны в грабежах и насилиях. Индейцы рассказывали, что каждый колонист обзавелся несколькими женами, начались раздоры, большая часть ушла внутрь острова и была перебита местным касиком (племенным вождем), который затем разрушил и сжег Навидад. Защитники форта, спасаясь бегством на лодке, утонули.
Колумб построил город к востоку от сожженного форта и назвал его Изабеллой (январь 1494 г.). Там появился новый враг — желтая лихорадка: «большая часть людей была поражена недугом». На разведку внутрь страны адмирал отправил небольшой отряд под командой Алонсо Охеды. Через несколько дней он вернулся с известием, что внутренние части острова густо населены мирными индейцами и что там есть богатые золотые россыпи: он принес образцы речного песка со значительным содержанием золота, найденного им в долине р. Яке-дель-Норте, у подножия гор Сибао (Кордиль-ера-Сентраль). В поисках золота 12—29 марта Колумб совершил поход внутрь о. Гаити, причем перевалил хр. Кордильера-Сен-траль (до 3175 м, высшая точка Антильских о-вов). В Изабелле его ожидало неприятное известие: большая часть съестных припасов испортилась из-за влажной тропической жары. Надвигался голод — следовало сократить количество едоков — и адмирал решил оставить на Эспаньоле только пять кораблей и около 500 человек. Остальных на 12 кораблях он отправил в Испанию под начальством Антонио Торреса с «Памятной запиской» для передачи королю и королеве.
Колумб доносил, что нашел месторождения золота, сильно преувеличивая их богатство, а также «признаки и следы всевозможных пряностей». Он просил прислать скот, съестные припасы и земледельческие орудия, предлагал покрывать расходы рабами, которых брался доставлять в большом количестве, понимая, что за товары для колонии нельзя платить одними надеждами на золото и пряности. «Памятная записка» — тяжелый обвинительный документ против Колумба, характеризующий его как инициатора массового обращения в рабство индейцев, как ханжу и лицемера: «...Забота о благе для душ каннибалов и жителей Эспаньолы привела к мысли, что чем больше доставят их в Кастилию, тем лучше будет для них... Их высочества соблаговолят дать разрешение и право достаточному числу каравелл приходить сюда ежегодно и привозить скот, продовольствие и все... необходимое для заселения края и обработки полей... Оплату же... можно производить рабами из числа каннибалов, людей жестоких... хорошо сложенных и весьма смышленых. Мы уверены, что они могут стать наилучшими рабами, перестанут же они быть бесчеловечными, как только окажутся вне пределов своей страны». По этому поводу Карл Маркс замечает: «[Разбой и грабеж — единственная цель испанских искателей приключений в Америке, как это показывают также донесения Колумба испанскому двору]. [Донесения Колумба характеризуют его самого как пирата]; ...[Работорговля как базис!]».
1 мая обнаружил узкий и глубокий залив, названный им Пуэрто-Гранде (современная бухта Гуантанамо). Далее к западу берег становился все гористее. «Ежечасно открывались перед ним чудеснейшие бухты и высокие горы...» Это была Сьерра-Маэстра с пиком Туркино (1974 м), самой высокой вершиной Кубы. Здесь он повернул на юг: по указаниям индейцев, «неподалеку [на юге] лежит остров Ямайка, где есть много золота...» (писал Б. Лас Ка-сас). Этот остров показался 5 мая. Колумб назвал его Сантьяго. Нагие индейцы, «раскрашенные в разные цвета, но большей частью в черный», с головными уборами из перьев, без страха подходили на челнах-однодеревках к кораблям, пытались помешать высадке. Колумб приказал стрелять по ним из арбалетов. «После того как шесть или семь индейцев были ранены, они сочли за благо прекратить сопротивление...» и к кораблям подошло много каноэ. «Индейцы привезли съестные припасы и все прочее, чем они владели, и охотно давали привезенное с собой... за любую вещь...»
Адмирал прошел вдоль северного берега Ямайки до 78° з. д. На острове не было «ни золота, ни иных металлов, хотя во всех прочих отношениях он казался раем», и Колумб 14 мая вернулся к Кубе, к мысу Крус. «Море было мелкое — они вошли в мелководный залив Гуаканаябо. Колумб осторожно продвигался на запад, и перед ним открылся странный архипелаг: чем дальше, тем чаще встречались на пути мелкие и низкие островки. Чем ближе к берегам Кубы, тем приветливее и зеленее казались они. Адмирал назвал их Хардинес-де-ла-Рейна («Сады Королевы»). 25 дней плыл Колумб на запад в этом лабиринте островов. Каждый вечер при штормовом ветре шел ливень с грозой. Моряки иногда целые сутки не смыкали глаз. Не раз киль корабля скреб дно. Вскоре показались горы — Сьерра-дель-Эскамбрай. Продвигаясь вдоль обрывистого берега к западу, адмирал пропустил узкий вход в бухту, где позже вырос порт Сенфуэгос, но обследовал бухту Кочинос («залив Свиней»— здесь в 1961 г. высадились и были разгромлены кубинские контрреволюционеры-эмигранты). Затем суда попали в мелководную акваторию — залив Батабано, заинтриговавший испанцев: вода в ней от движения волн становилась то белой, как молоко, то черной, как чернила1. Мангровые заросли по берегам залива были, по словам Колумба, настолько «густы, что даже кошка не смогла бы достичь берега». 27 мая суда прошли западную оконечность болотистого п-ова Сапата, а 3 июня испанцы высадились на заболоченный северный берег залива Батабано (у 82°30' з. д.).
К западу (у 84° з. д.) море сильно обмелело, и Колумб решил возвращаться: суда давали течь, матросы роптали, провизия была на исходе. Под присягой почти от каждого члена экипажа 12 июня 1494 г. он получил показания, что Куба — часть континента и, следовательно, дальше плыть бесполезно: острова такой длины существовать-де не могло. В действительности же адмирал находился почти в 100 км от мыса Сан-Антонио, западной оконечности о. Куба. Общая длина открытого им южного кубинского побережья составила около 1700 км. Повернув на восток, Колумб обнаружил большой о. Эванхелиста (Пинос, 3056 км2) и простоял там около двух недель, чтобы дать отдых людям. С 25 июня по 18 июля он шел на юго-восток через то же усеянное островами море к мысу Крус. «При этом особенно досаждали ему ливни, которые обрушивались на корабли каждый вечер». После отдыха на мысе Крус он пытался идти прямо на Эспаньолу, но из-за противных ветров вынужден был 22 июля вернуться к Ямайке. Он обогнул с запада и юга «эту зеленую, прекрасную и счастливую землю... За кораблями следовали бесчисленные каноэ, и индейцы служили христианам, давая им еду, словно пришельцы были их родными отцами... Однако каждый вечер бури и ливни донимали команды кораблей». К счастью, 19 августа установилась хорошая погода, и на следующий день Колумб пересек пролив Ямайка и подошел к юго-западному выступу Эспаньолы. 40 дней он обследовал побережье этого острова, еще не посещенное испанцами, и только 29 сентября вернулся в г. Изабеллу, истомленный и тяжело больной. Болел он пять месяцев.