Утром 18 ноября флотилия отплыла от Сан-Томаса на север и в тот же день увидела новый остров, который Адмирал назвал Грациоза по имени доброй матери друга своей юности, которая щедро помогала ему в его бедности. Но это название не уцелело и со временем было заменено на прозаическое Вьекес, ставший частью Пуэрто-Рико. Именно к этому острову — самому крупному из всех, что были уже открыты в этом плавании, который местные жители называли Борикен, а Колумб переименовал в честь Святого Иоанна Крестителя, назвав его Сан-Хуан, и направились теперь его каравеллы. Однако южная часть острова оказалась скалистой, а достигнутая после обхода его юго-западной оконечности западная сторона на длительном расстоянии была ограждена опасными рифами, что заставило флотилию долго искать надежного подхода к берегу, который и был найден в заливе Аняско, куда впадала одноименная река. Остров был довольно густо населен, но контакта с индейцами в этот раз испанцам установить не удалось, так как напуганные постоянными нашествиями жестоких карибов местные жители растворились в густых тропических зарослях острова еще при обнаружении страшных судов неизвестных пришельцев.
Завершив первое ознакомление с новым островом, Колумб направил каравеллы через узкий пролив Мона и к вечеру 22 ноября высадился на восточном берегу уже знакомой Эспаньолы. Побывавшие в цивилизованной Испании индейцы с ликованием встретили возвращение в родные края. Один из них был почти у себя дома и показал Адмиралу путь к своей деревне, где его высадили, щедро снабдив мелкими подарками для соплеменников, которые уже на следующий день вели бойкую торговлю-обмен с прибывшими испанцами. Колумб спешил поскорее встретиться с оставленными им почти год назад жителями поселка Навидад и теперь уже знакомым ему берегом повел флотилию к заливу Караколь, прохода к которому она достигла к вечеру 27 ноября. Помня урок разбившейся ночью в тех водах первой «Санта-Марии», Адмирал поставил каравеллы на якорь на подступах к бухте в ожидании утра.
Чтобы дать знать о своем прибытии жителям поселка, он приказал запустить световые ракеты и сделать пушечные выстрелы. Однако никакой реакции из Навидад на эти сигналы не последовало. Совсем поздно вечером к капитане приблизилось каноэ с индейцами, которые криками стали вызывать Адмирала. Когда он появился на палубе, они передали ему подарки от его друга Гуаканагари и заверили его, что за исключением нескольких умерших все жители Навидад были живы и здоровы. Однако в личной беседе с ними индеец-переводчик Диего смог выведать столь страшную правду об их судьбе, что испанцы вначале не могли в нее поверить.
Как оказалось, после отбытия Колумба в Испанию двое из назначенных им руководителей общины Навидад организовали оставшихся людей в банды, которые прочесывали территорию Эспаньолы в поисках золота и женщин, вызывая недовольство и возмущение, а затем и сопротивление индейцев, которые до этого обеспечивали испанцев всем необходимым, передавая им в том числе и имевшееся у них золото. Особенно много неприятностей они доставили вождю Каонабо, племя которого проживало в центре острова. Доведенный до отчаянья бесчинствами испанцев, он во главе своих воинов сначала уничтожил мародерствующую банду королевского представителя Гутьереса, а затем напал на Навидад, где оставалось всего 10 человек для охраны укрепленного форта. Здесь испанцы были легко разгромлены, а те из них, кому удалось выбраться в окружающие заросли, были найдены и уничтожены. Этим самым было положено начало большим проблемам между невинными местными жителями и хищными пришельцами, что радикальным образом изменило положение на острове.
Рассчитывая по-прежнему на расположение к нему касике Гуакагарани, Колумб в первом порыве хотел приступить к восстановлению поселка Навидад. Однако врач экспедиции, познакомившись с местностью, сразу же высказал свои возражения, так как установил ее опасный малярийный характер и плохое качество питьевой воды ее источников. Кроме того, поселок оказывался расположенным далеко от главного обнаруженного района добычи золота. С учетом этих соображений Адмирал решил найти более благоприятное место для нового поселения, где готовились жить 2–3 сотни колонистов. Каравеллы снялись с якоря и направились вдоль берега Эспаньолы на восток. После почти месяца чрезвычайно трудного плавания против сильного встречного ветра и течения и пройдя всего 32 мили, утомленные экипажи и колонисты, потерявшие значительную часть привезенных из Испании домашних животных, наконец вошли в несколько защищенную бухту. Здесь Колумб довольно спешно принял решение основать новое поселение, назвав его в честь своей королевы «Изабелла».