Мало-помалу «адмиралу моря-океана» удалось вернуть расположение кастильского двора. Фердинанд поневоле должен был отказаться от своего предвзятого мнения о Колумбе, как увлекающемся энтузиасте. В конце концов обещание адмирала сбылось: Эспаньола стала приносить королевской казне значительные доходы. В Испанию прибывали из Эспаньолы корабли, груженные золотом. Привозили оттуда и жемчуг.
Правда, официальный титул вице-короля Колумбу так и не был возвращен, но это объясняется не столько его личными взаимоотношениями с Фердинандом и Изабеллой, сколько интересами кастильской короны, превратившей, несмотря на договор с Колумбом, всю торговлю колонии в королевскую монополию.
Вместо отозванного Бовадильи на Эспаньолу был послан новый королевский наместник Николас Овандо, возглавивший флотилию из двадцати трех кораблей, которые перевезли за океан около трех тысяч поселенцев. В годы наместничества Овандо коренное население Эспаньолы и других островов Большого Антильского архипелага еще более сократилось. Недостаток рабочей силы в колониях испанцы стали восполнять черными рабами – африканскими неграми, количество которых увеличивалось на островах с каждым годом. По приказанию королей Овандо ввел на Эспаньоле новый порядок: каждый колонист обязан был вносить в казну одну треть добытого золота.
Христофору Колумбу исполнилось шестьдесят шесть лет. Ему не терпелось отправиться в четвертое путешествие. Он твердо надеялся достигнуть Индии через «Западный океан» – более безопасным и более коротким путем, нежели Васко да Гама, обогнувший мыс Доброй Надежды. Колумб был убежден, что открытые им земли составляют часть азиатского материка и завоеванные им острова отделены только проливом от Золотого Херсонеса (полуостров Малакка), откуда уже легко будет добраться до настоящей Индии и создать конкуренцию португальской торговле. Таким образом, развенчанный вице-король вновь превращался в отважного адмирала. На этот раз Колумб задумал осуществить кругосветное плавание. Несмотря на то, что многие кастильские вельможи возражали против этого плана, считая его несбыточным, Фердинанд и Изабелла рассудили, что риск для них не столь уж велик, а приобретут они многое, если Колумбу удастся его предприятие.
Было решено снарядить флотилию из четырех кораблей. Назывались они «Капитаны», «Сантьяго де Палос», «Гальега» и «Вискайна». Суда были небольшие, водоизмещением в пятьдесят – семьдесят тонн. По существу это были корабли каботажного плавания.
14 марта Колумбу была вручена королевская инструкция, которая во многом ограничивала его права и ставила все его действия под контроль нотариуса и еще одного должностного лица – Франсиско де Порраса, являвшегося одновременно капитаном «Гальеги». Франсиско де Поррас должен был принимать от адмирала в присутствии нотариуса «все, что будет добыто и приобретено… будь то золото, серебро, жемчуг, драгоценные камни и пряности или иные ценности». Вместе с тем Фердинанд и Изабелла запретили Колумбу высаживаться на Эспаньоле, а Николасу Овандо, правителю острова, было еще раньше предписано не допускать туда Колумба.
9 мая 1502 года Христофор Колумб вышел из Кадиса, имея на борту всех четырех кораблей около ста пятидесяти человек экипажа. Вместе с ним отправлялись в далекий путь его брат Бартоломе и тринадцатилетний Эрнандо, сын Колумба от второго брака.
20 мая корабли Колумба остановились в гавани Гран-Канария, а 15 июня достигли Мартиники, одного из наветренных островов Малого Антильского архипелага. Затем Колумб заходил на острова Доминика, Санта-Крус, Борикен (Пуэрто-Рико) и, наконец, 29 июня, после благополучного плавания, достиг острова Эспаньола.