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