Почти одновременно с прибытием флотилии Торреса в Кадис Колумб отправился из строившейся еще Изабеллы во главе большого вооруженного отряда в несколько сот человек, облаченных в боевые доспехи, в глубь Эспаньолы для обследования ее территории. Желая произвести самое большое впечатление на местных жителей в надежде, что они могут находиться поблизости от столицы или крупного города Великого восточного Хана, при подходе к каждому местному поселению отряд развертывал знамена под барабанный бой и сопровождение труб. Такого рода торжественные боевые процессии испанцы впоследствии станут повторять и при покорении других частей нового континента Хотя отсутствие Великого Хана вновь вызвало разочарование Адмирала, а 29-дневный поход по красивейшим горам и долинам острова был омрачен очень плохой погодой, полуголодным пропитанием, недостатком питьевой воды и отравлениями, некоторое количество золота испанцам удалось собрать, что помогло им преодолеть выпавшие на них невзгоды. Колумб оставил в стратегически расположенном месте маршрута крупную часть своего отряда во главе с офицером Маргарит для возведения форта. При возвращении в Изабелу он обнаружил очень тревожное положение среди оставленных там людей: многие из них болели из-за нездорового климата местности, все они голодали по причине почти полностью закончившихся запасов продуктов, все были страшно недовольны, а большинство были на грани мятежа. Опасаясь восстания, Адмирал распорядился перенести все оружие и боеприпасы на свой флагман под наблюдение брата Диего.

Чтобы снять напряжение в поселке и занять его людей поисками вожделенного золота, Колумб формирует новый отряд в 400 человек под командованием Алонсо Охеда и отправляет его на смену строителей форта. Как первый, так и второй из этих отрядов, несмотря на требования Адмирала выполнять приказ королей о добром обращении с туземцами, занялись самыми настоящими бесчинствами, силой отнимая у индейцев имевшиеся у них продукты и золото, уводя мальчиков как рабов, а девочек и девушек в качестве заложниц. Местное население было приведено в отчаяние такими бесчинствами пришельцев и готовилось к сопротивлению и возмездию. После ухода отряда Охеды сам Колумб, ничего не зная о происходящем, стал спешно готовиться к продолжению исследования Кубы, Когда суда были подготовлены, он покинул Эспаньолу, оставив брата Диего — мягкого, миролюбивого и слабовольного человека — командовать недовольствующими колонистами и бесчинствующими вояками.

Адмирал отплыл из Изабелы 24 апреля 1494 года на выносливой «Нинье» в сопровождении еще двух небольших каравелл. Вместе с ним находились замечательный лоцман и картограф Хуан де Ла Коса, еще несколько участников первого плавания и незаменимый переводчик Диего. Двигаясь с попутным ветром и благоприятным течением по знакомому маршруту, маленькая флотилия уже через пять дней пересекла пролив между Эспаньолой и Кубой. Колумб высадился на обследованном в первом плавании мысе Альфа и Омега (сегодня мыс Майей), где вступил во владение островом от имени своих монархов, проведя обычную для таких случаев торжественную церемонию с возведением большого креста и зачитыванием установленного протокола

Уже на следующий день Адмирал решает обследовать Кубу вдоль ее южного берега, следуя теории Аристотеля и опыту португальцев, а также советам собственных офицеров, которые говорили, что в южных краях бывает больше всего полезного, в том числе и золота, чем в северных. Впереди теперь снова лежали неизведанные земли и новые открытия. К вечеру уже первого дня пути в юго-западном направлении каравеллы обнаружили великолепную глубокую бухту, которую Колумб назвал Большим Портом — будущую гавань Гуантанамо. Здесь на берегу они увидели большую толпу индейцев-таинов, готовивших огромное угощение в честь гостившего у них соседнего касике. Как бывало и прежде, появление пришельцев в их заливе вызвало невероятную панику среди туземцев, которые сразу же разбежались в окружающие заросли. Однако Диего-переводчику вскоре удалось убедить своих сородичей в мирных намерениях пришельцев, и они постепенно вернулись к продолжению празднества, но теперь уже вместе с испанцами, от которых получили много обрадовавших их традиционных безделушек в качестве подарков.

Утром 1 мая путешественники продолжили плавание вдоль высоких скалистых берегов Кубы, часто встречая толпы приветствующих их индейцев, которые собирались у кромки воды или выплывали на каноэ в море Всего после 40 миль пути перед каравеллами появилась еще одна великолепная бухта — место скорой закладки первого будущего кубинского города Сантьяго-де-Куба Местные индейцы приняли испанцев с большим восторгом и радушием. От них Адмирал узнал, что в юго-западном направлении от их бухты находился большой остров, который они называли «Хамайка» (Ямайка). Здесь испанцы провели ночь, а с рассветом 2 мая продолжили поход на запад, двигаясь и наступившей ночью. На следующий день они достигли резко обозначенного мыса, получившего от Колумба название мыса Креста, у которого береговая линия резко поворачивала на северо-северо-восток. До сих пор Адмирал не смог обнаружить на Кубе каких-либо ожидаемых по сведениям Марко Поло признаков Японии или Китая. Не было здесь и свидетельств присутствия золота, что и побудило его в тот же день круто повернуть курс на юго-юго-восток в сторону Ямайки

К этому времени погода резко переменилась из-за поднявшегося сильного ветра, но к концу второго дня пути она вновь успокоилась, и каравеллы смогли войти в залив, названный Колумбом Санта-Глория, переименованный впоследствии англичанами в Св. Анну. Ямайка оказалась чрезвычайно живописным гористым островом с большим количеством населения тайно. Однако в отличие от своих кубинских соплеменников здешние индейцы встретили белых пришельцев с воинственной враждебностью. Против их стрел сначала пришлось применить холостые пушечные выстрелы, а затем огнестрельное оружие и даже большую злую собаку, которая доставила тайно много серьезных неприятностей. В конечном счете они вынуждены были предоставить испанцам имевшееся у них продовольствие, но золота на острове не оказалось, и Адмирал решил после еще одной короткой стоянки в сегодняшнем заливе Монтиго вновь вернуться к мысу Креста на Кубе.

Сейчас каравеллы всего за один день пути достигли этого мыса и 14 мая уже продолжали обследовать кубинское побережье. Здесь уже в начале плавания на пути путешественников возникла широкая полоса мелких красивых островов со множеством мангровых зарослей, наполненных массой тропических птиц и опьяняющих ароматных запахов. Колумб назвал этот островной архипелаг Садами Королевы, через которые, однако, пробираться каравеллам было совсем нелегко. Выбравшись из этого островного мелководья, суда направились вдоль берега к видневшейся на горизонте горной гряде, а затем встали на якорь у живописного песчаного пляжа залива Свиней, где в 1961 году в окружающих болотах был разгромлен десант кубинских контрреволюционеров.

В этом заливе путешественники обнаружили источники очень вкусной пресной воды, которая пробивалась на поверхность моря недалеко от побережья, что позволяло пополнять ее запасы без выхода на сушу. Продвинувшись еще дальше на запад, европейцы обнаружили еще одно удивительное явление, когда морская вода вдруг становилась мутно белой, а затем черной. Как выяснилось в уже более поздние времена, белый цвет на мелководье воде придавал переворачиваемый волнами мергель, а черный возникал благодаря поднимавшемуся со дна мелкому песку такого же цвета