Продвинувшись немного дальше на северо-запад, вдоль берега Кубы, адмирал высадил двух послов, приказав им разыскать внутри страны туземного царя и завязать с ним сношения. Один из послов говорил по-арабски, но в этой удивительной стране никто не понимал "даже" арабского языка, распространенного, по мнению Колумба, по всей Азии. Послы нашли селения с большими жилищами из ветвей и тростника, окруженные возделанными полями. Только одна культура была им знакома - хлопчатник: в домах женщины ткали из хлопка грубые ткани или скручивали из пряжи сети. Мужчины и женщины, встречавшие пришельцев, "шли с головнями в руках и с травой, употребляемой для курений". Так европейцы впервые увидели, как употребляют табак, а незнакомые культурные растения оказались маисом (кукурузой), картофелем и табаком, которые позднее распространились по всем обитаемым материкам.
Затратив две недели на ремонт судов, Колумб прошел вдоль Кубы дальше на северо-запад, пока не достиг прибрежных островов, которые он назвал "Садами короля" (теперь Камагуэй). Страна была очень слабо заселена. Дальнейшее плавание в северо-западном направлении вдоль "китайского" берега казалось Колумбу бесцельным. Он думал, что случайно достиг самой бедной части Китая. Зато на восток от Китая должен был лежать "богатейший остров" Япония. И Колумб повернул обратно, на юго-восток,
В это время Мартин Пинсон скрылся со своей "Пинтой". Колумб подозревал измену: он предполагал, что старший Пинсон хотел лично для себя открыть золотые россыпи, о которых сообщали пленные индейцы. Еще две недели после бегства "Пинты" Колумб медленно шел в восточном направлении, пока не достиг оконечности Кубы. 6 декабря, потеряв из виду Кубу, он открыл большой остров, который местные жители называли Гаити. Колумб дал ему имя Эспаньола (Испанский остров), так как там вдоль берега "тянутся прекраснейшие в свете долины, весьма похожие на земли Кастилии, но во многом превосходящие последние".
На Эспаньоле встречалось больше золота, чем на других островах: моряки видели у индейцев тонкие золотые пластинки и небольшие слитки. Среди экипажа усиливалась "золотая лихорадка". В дневнике Колумба появляются первые записи о грабежах: "...испанцы так жадны и ненасытны, что не удовлетворялись, когда индейцы за... осколок стекла, черепок разбитой чашки или иные никчемные вещи давали им все, что только они желали. Но даже и не давая ничего, испанцы стремились взять и захватить все".
Впрочем, самого генуэзца тоже "лихорадило". На следующий день после этой гневной характеристики испанцев Колумб записывает: "Владыка наш в своем милосердии пошлет мне удачу и я найду... золотую копь". Он заносит также слова старика-индейца об одном острове, "сплошь золотом", и о других островах, где "золото собирают и просеивают через сито, а затем плавят и выделывают из него разные вещицы".
К несчастью, 25 декабря, в день рождества, из-за небрежности вахтенного офицера адмиральский корабль сел на мель. Морякам удалось с помощью туземцев снять с "Санта-Марии" весь ценный груз, пушки и припасы. В распоряжении Колумба оставалась только маленькая "Нинья". На ней нельзя было поместить команды двух кораблей, и адмирал решил часть людей оставить на острове, а на "Нинье" спешно вернуться в Испанию. 39 испанцев добровольно остались на Эспаньоле, так как надеялись найти много золота. Колумб приказал из обломков разбитого корабля построить форт, вооружил его пушками, снятыми с "Санта-Марии", и снабдил припасами на год. Этот первый европейский поселок в Новом Свете, возникший в результате рождественской катастрофы, был назван Навидад (Рождество).
Выйдя из гавани Навидад на восток, Колумб через два дня встретил "Пинту". Мартин Пинсон уверял адмирала, что "покинул флотилию против своей воли". Адмирал притворился, что верит Мартину, так как "не время было карать виновных": экипаж "Пинты" был на стороне своего капитана, а "Ниньей" командовал его родной брат - Висенте Пинсон. 16 января оба судна вышли в открытый океан и взяли курс на Палое.
Первые четыре недели плавания прошли благополучно, но затем начался шторм. В ночь на 14 февраля "Нинья" потеряла из виду "Пинту". "С восходом солнца ветер усилился и волнение на море стало еще более грозным... Никто не думал, что удастся избежать неминуемой гибели..." Колумб думал в эти дни тяжелую думу: если "Нинья" пойдет ко дну, то никогда христианский мир не узнает о его великом открытии. Он написал об открытии на пергаменте, обернул его провощенной тканью, вложил сверток в бочонок и бросил в море. Буря продолжалась четыре дня. На рассвете пятого дня, когда ветер немного стих, моряки увидели землю - один из Азорских островов (Санта-Мария).