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