Попасть малоизвестному человеку на аудиенцию к любому королю — дело далеко не простое, тем более для иностранца. Но Колумб жил в Португалии уже с 1576 года, где вместе с братом Бартоломео работал в мастерской по изготовлению географических и навигационных карт и где у него сформировался его радикальный план достичь Индии западным морским путем. Именно из Лиссабона он совершает свои дальние атлантические плавания, набираясь большого опыта в навигации, изучая превалирующие океанские течения и направления ветра в разных широтах Атлантики, перенимая опыт и сведения в мореходном деле от португальцев — самых передовых мореходов Европы. Здесь же в Лиссабоне Христофор женится на португальской аристократке из очень влиятельной семьи донье Фелипе ди Перетрельу.
Лиссабон стал также тем местом, где Колумб окончательно отрабатывает свой дерзновенный проект. Еще при предшественнике Жоау Второго короле Альфонсе Пятом генуэзскому мореходу и картографу становится известно, что португальский монарх находится в контакте с выдающимся флорентийским географом Тосканелли. Тот король, столь активно продолжавший дело Энрике-Мореплавателя и несколько озабоченный медленным продвижением его мореходов вдоль берегов Африки, интересовался у ведущего представителя науки того времени его мнением относительно наиболее короткого морского пути в Индию. Согласно сохранившимся письмам и картам, в своих ответах королю Тосканелли полагал, что таким путем является маршрут из Европы через Атлантику на Запад и что на этом пути должны быть острова Речь фактически шла о возможности совершения кругосветного путешествия. Чтобы подтвердить эту идею, Колумб обменивается письмами с Тосканелли, что помогает ему еще больше уверовать в правоту своего плана. Он начинает готовиться представить его португальскому государю. Благодаря связям родственников доньи Фелипе со двором после продолжительных ожиданий Колумб получает, наконец, разрешение на такую аудиенцию в 1483 году. Король внимательно и вежливо выслушал предложение Колумба и затем передал его на рассмотрение группе своих ученых советников. После тщательного изучения ими плана генуэзца они единодушно рекомендуют его отклонение как научно необоснованного и практически неосуществимого. К этому времени португальские каравеллы выходят к берегу сегодняшней Нигерии и возводят там форт Сау-Жоржи-да-Мина, через который начинает поступать такое количество золота и черных рабов из африканских стран, что они становятся важным фактором экономики страны. На фоне этих свершений Колумб получает отказ, но не расстается со своим планом. Рассчитывая со временем на улучшение его перспектив при дворе Лиссабона, он продолжает терпеливо ждать и не прекращает поиск влиятельных людей для поддержания своей идеи перед монархом.
Перспективы этих трудных и мучительных ожиданий значительно ухудшаются ввиду состоявшегося возвращения в 1484 году Диогу Кау из длительной экспедиции, которая, по его утверждению, достигла южной оконечности Африки, практически подведя португальцев к заключительному этапу выхода к берегам Индии. В этих обстоятельствах Колумб понимает невозможность принятия его предложения Жоау Вторым. Продолжал, однако, верить в правильность своей идеи, он решает убедить в ней королевскую чету Испании — королеву Кастилии Изабеллу и короля Арагона Фердинанда, брак которых положил начало объединению испанских земель Иберийского полуострова в новое государство — Испанию.
Христофор Колумб покидает Португалию, где он прожил почти 10 лет, примерно в 1485 году. К этому времени он овдовел и остался вдвоем со своим сыном Диего. Его финансовое положение было просто плачевным. Он, видимо, был обременен и немалыми долгами. У него тогда не было даже костюма или мула, соответствующих его социальному положению Пешком и на перекладных они с сыном добираются до небольшого порта Палое на южном берегу Испании и находят приют в монастыре в местечке Ла Рабида Здесь он близко сходится с настоятелем монастыря монахом-францисканцем отцом Антонио Марчена. Часто встречаясь с ним для бесед, Колумб с заразительной убедительностью и страстью излагает перед ним свой проект западного морского пути в Индию и делится своими расстроенными чувствами в связи с невозможностью найти необходимую поддержку его осуществлению. Отец Антонио постепенно не только становится горячим и убежденным сторонником плана Колумба, но и привлекает на его сторону ряд знакомых ему влиятельных аристократов и служителей церкви высокого ранга, в том числе советника при свите короля Луиса Сантанхеля. Вот что писал впоследствии об этой страстной убежденности Колумба в его проекте монах, а затем архиепископ Лас Касас, хорошо лично знавший генуэзца: «Он был настолько уверен в открытии того, что затем открыл, и в нахождении того, что потом нашел, что казалось, будто у него все это находится в его комнате под его ключом». Благодаря неустанным стараниям всех этих людей после многочисленных попыток, разочарований и ожиданий Колумбу удается все-таки получить обещание на королевскую аудиенцию.