Именно в это время вместе с четырьмя каравеллами с провиантом на Эспаньолу из Испании прибыл специальный представитель королей. Хуан Агуадо — бывший колонист, вернувшийся ранее с капитаном Торресом в родные края, — теперь имел высочайшее поручение расследовать положение на острове и сделанные против братьев Колумбов жалобы и обвинения. Осознав, наконец, всю серьезность сложившегося положения, Адмирал поспешил отправиться в Испанию, оставив вместо себя брата Барголомео. 10 марта 1496 года он отплыл на испытанной «Нинье» в сопровождении небольшой каравеллы «Индиа», собранной на Эспаньоле из остатков разбитых ураганом других судов. На них в страшной тесноте разместились 225 испанцев и 35 рабов-таино. Торопясь ускорить возвращение, Колумб решил избрать самый короткий по расстоянию маршрут и направился к Гваделупе, где собирался пополнить запасы перед выходом в открытый океан. Однако преодолевая встречные ветры и течения, этот переход потребовал почти целый месяц. На самом же острове испанцы были встречены воинственными карибами, которых они буквально принудили дать им некоторое местное продовольствие, взяв в плен нескольких заложников.

Каравеллы смогли покинуть живописную, но негостеприимную Гваделупу только 20 апреля и сразу же встретились с сильным встречным ветром, который так быстро доставил флотилию второго плавания в Индии осенью 1493 года. Почти целый месяц тяжелого перехода при полуголодном существовании понадобился Адмиралу, чтобы вывести суда к югу от Азорских островов, где они удачно подхватили западный ветер, который значительно ускорил их продвижение к берегам Испании. За эти три последние недели пути испанцы так сильно страдали от голода, что несколько раз серьезно обсуждали вопрос о том, чтобы начать есть нескольких прихваченных на Гваделупе карибов. Лишь решительное вмешательство Колумба предотвратило такое людоедство со стороны окончательно изголодавшихся европейцев.

Это труднейшее плавание через океан завершилось для двух истрепанных каравелл и их до безумия голодных экипажей в бухте Кадиса 11 июня 1496 года, откуда огромная флотилия Адмирала с радужными надеждами и сытыми желудками вышла в Атлантику два года и девять месяцев тому назад. С точки зрения открытия новых островов, включая многочисленный Малый Антильский архипелаг, Пуэрто-Рико, Ямайку и южное побережье Кубы, Колумб мог испытывать большое удовлетворение итогами своего второго путешествия. Однако во всех остальных задачах, поставленных перед ним его суверенами, это плавание было скорее совсем неудачным: Китай или Япония обнаружены не были; колония Изабела оказалась нежизнеспособной, и ей уже нужно было искать срочную замену; больших залежей золота на острове тоже не оказалось; обращение тайно в христианство уступило их порабощению и уничтожению, а недовольство действиями братьев Колумбов и жалобы на них со стороны колонистов превратились в такой громкий поток, что короли стали серьезно подумывать над тем, чтобы полностью прекратить с ними отношения. Удрученный этими событиями Колумб при прибытии в Кадис надел на себя в порядке покаяния грубое платье монаха-францисканца и, отказываясь от светских приглашений, посещал религиозные заведения Севильи, в тревоге ожидая королевского вызова прибыть ко двору для обсуждения сложившегося серьезного положения в Индиях.

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

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

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

Теперь после долгих проволочек они отдали Адмиралу распоряжение приступить к подготовке третьей экспедиции и согласились подтвердить искомые им права, привилегии и титулы. На этот раз флотилия должна была состоять из шести каравелл, трем из которых предстояло перевезти необходимые товары и продукты прямо на Эспаньолу в Санто-Доминго — новое поселение, выбранное братьями Колумбами вместо оставленной ими нездоровой Изабеллы. На них предусматривалось также отправить за королевский счет свыше 300 новых колонистов. Их ряды должны были пополнить 30 женщин — первых эмигранток из Старого Света в Новый. Три другие каравеллы предназначались для совершения новых открытий. Однако развенчание репутации Индий в результате второго плавания создало на этот раз немалые трудности в нахождении добровольцев, что заставило организаторов экспедиции брать помилованных в этих целях уголовников при обязательстве прожить на Эспаньоле в течение 1—2 лет. К концу мая 1498 года все основные приготовления были завершены, и все шесть парусников вышли из Севильи вниз по Гвадалквивиру в Сан-Лукар-де-Баррамеда. Здесь Колумб поднялся на свой новый флагман «Санта-Мария-де-Гиа», и началось его третье трансатлантическое плавание. Это был последний день мая 1498 года

Руководствуясь главной задачей начавшегося путешествия найти новый континент и следуя укоренившемуся тогда поверью, что в южных широтах имеется больше золота, Адмирал прокладывает маршрут примерно до широты Сьерра-Леоне, где португальцы нашли крупные золотоносные шахты. Сначала он делает остановку на Мадейре, затем на Канарских островах и потом заходит на острова Зеленого Мыса, каждый раз восполняя свои запасы. Плавание проходило без особых проблем, и после последней заправки 7 июля каравеллы направляются через Атлантику, беря курс на юго-запад при попутном ветре. Но через неделю бодрого хода флотилия попадает в длительную полосу полного безветрия, которая продолжалась целых 8 дней, заставляя каравеллы дрейфовать по экваториальному течению. Но затем поднялся великолепный попутный ветер, и 31 июля Колумб правильно определил, что он достиг меридиана Малых Антильских островов. Учитывая кончавшиеся запасы питьевой воды, Адмирал решает повернуть на северо-восток, где по его расчетам недалеко должна была быть Доминика. Несколько позднее в тот же день один из его слуг радостным громким криком сообщил экипажу капитаны, что к западу от нее по борту он видит землю в форме трех холмов, которые и определили по желанию Колумба название нового острова Тринидад, то есть Троица.