Колумб оставил в форту Навидад тридцать девять добровольцев, назначив своими заместителями Диего де Арану, Перо Гумьереса и Родриго Эсковеду. «Среди прочих людей, что остались на острове, были корабельный плотник, конопатчик, хороший пушкарь, знающий толк в фортификации, бондарь, портной, лекарь». Оставшиеся в Навидаде испанцы были обеспечены припасами на целый год.
Поручив гарнизону форта во что бы то ни стало отыскать золотые россыпи и выбрать место, подходящее для постройки города, Колумб, простившись с касиком и с первыми поселенцами, 3 января снялся с якоря и отчалил от гавани на каравелле «Нинья».
На другой день Колумб открыл небольшую бухту, рядом с которой находилась высокая гора. Это место, удобное для стоянки, он назвал Монте-Кристи (гора Христа). 6 января один из матросов увидел с верхушки мачты каравеллу «Пинта». Капитан «Пинты» Мартин Алонсо Пинсон вскоре поравнялся с «Ниньей» и, явившись к Колумбу, стал оправдывать перед ним свое поведение; он утверждал, что его отлучка была вынужденной. На самом деле Пинсон, как и предполагал Колумб, решил первым достигнуть легендарного острова Банеке и захватить золотые россыпи. Адмирал не возражал против подобных объяснений капитана Пинсона, убедившись, что «Пинта» всего лишь крейсировала вдоль берегов Эспаньолы, не приблизившись ни к какому другому острову.
Седьмого января пришлось сделать остановку, чтобы закрыть течь на каравелле «Нинья». Воспользовавшись стоянкой, Колумб решил исследовать широкую реку, протекавшую в одном лье от Монте-Кристи. В ней были найдены золотые песчинки, и адмирал назвал ее «Золотой рекой». Колумбу хотелось продолжить исследование побережья Эспаньолы и прилегающих островов, но матросы, подстрекаемые братьями Пинсон, открыто высказывали свое недовольство и требовали скорейшего возвращения в Испанию.
Девятого января корабли снова снялись с якоря, продолжая следовать вдоль восточных берегов Эспаньолы. Но затем флотилия, задержанная безветрием, бросила якорь в удобной бухте, и здесь произошла стычка испанцев с туземцами, не проявившими на сей раз добрых намерений. 13 января испанские матросы пустили в ход оружие. Потеряв несколько человек, туземцы обратились в бегство. Так впервые европейцами была пролита кровь беззащитных индейцев.
На следующий день Христофор Колумб задержал на борту четырех молодых туземцев и, несмотря на их протест, дал приказ об отплытии. Экипажи каравелл, озлобленные и измученные, доставляли ему серьезные огорчения, на что горько сетует в своем дневнике этот стоявший над всеми человеческими слабостями человек, которого не могли сломить удары судьбы.
Наконец 16 января скрылся из виду последний мыс Эспаньолы, и обе каравеллы направились на восток. Подгоняемые попутным ветром, они, выйдя в открытый океан, быстро продвигались в нужном направлении. День тянулся за днем без всяких происшествий. Но 12 февраля, когда Колумб уже надеялся вскоре увидеть берега Испании, поднялась сильная буря и море начало так волноваться, что, по словам адмирала, не будь «Нинья» столь прочной и хорошо приспособленной для плавания, он серьезно опасался бы за ее судьбу.
Буря не прекращалась в течение четырех суток, ежеминутно угрожая кораблям гибелью. Испуганные моряки давали обеты отправиться босиком замаливать свои грехи в самые отдаленные монастыри, а буря между тем не унималась. Каравеллы бросало из стороны в сторону. Ветер угнал «Пинту» далеко на север, и она снова скрылась из виду. Оставшись на маленькой «Нинье», Колумб поторопился написать на пергаменте отчет о своих открытиях с просьбой к нашедшему доставить его королю Фердинанду и королеве Изабелле. «Этот пергамент он обернул провощенной тканью, как следует перевязал, приказал принести большой деревянный бочонок и вложил в него сверток — так, чтобы ни одна живая душа не знала, что содержится в нем, и все думали, что адмирал выполняет какой-то обет, а затем велел бросить бочонок в море».
Пятнадцатого февраля поутру буря стала стихать. К вечеру на горизонте была замечена земля, которая оказалась одним из островов Азорской группы. Радость Колумба и его спутников, снова увидевших землю Старого Света, была беспредельной, но прошло еще три дня, прежде чем им удалось пристать к острову Санта-Мария, самому южному в Азорском архипелаге.
На другой день экипаж «Ниньи» решил отслужить благодарственный молебен, и Колумб отпустил на берег половину всех матросов. Но едва только испанцы дошли до часовни, как их захватили в плен португальские солдаты, посланные губернатором острова. Когда попытка захватить также и Колумба с его каравеллой не увенчалась успехом, губернатор после настойчивых требований Колумба через пять дней освободил его матросов, и 24 февраля «Нинья» снова пустилась в море.