コロンブスはリスボンから海路、スペインのパロスに着き、そこからウエルバのティント川沿いの丘に建つラ・ラビダ修道院を訪ねた[注 12]。5歳の息子ディエゴを伴った彼を招き入れた修道院長のフアン・ペレス・デ・マルチェーネ神父はコロンブスの話に感銘を受け、彼に天文学者でもある[18]セビリアのアントニオ・マルチェーナ神父を紹介し、そこへ向かうために息子ディエゴを修道院で預かった。さらにコロンブスはスペイン貴族の第2代メディナ＝シドニア公爵ドン・エンリケ・デ・グスマン（スペイン語版）[16]、そして初代メディナセリ公爵（スペイン語版）（5代メディナセリ伯爵（スペイン語版）[18]）ドン・ルイス・デ・ラ・セルダ（スペイン語版）[16]と面会する機会を得た。メディナセリ公は興味を抱き、コロンブスが求めた数隻の船や食料など3,000 - 4,000ドゥカート相当の物資を準備することに合意した[18][2- 3]。コロンブスが作成したと言われる地図。これは19世紀に発見されたものだが、アイスランドとフェローズ諸島の位置が逆になっているなど、疑問も提示されている[19]。
カトリック両王への売り込み

コロンブスへの援助に同意したメディナセリ公だったが、このような計画は王室への許可を得るべきだと考えカスティーリャのイサベル1世へ計画を知らせると、彼女自身がこれに興味を覚えた[16]。1486年5月1日[注 13]、メディナセリ公が紹介してコロンブスはコルドバでイサベル1世とその夫フェルナンド2世（カトリック両王）に謁見した。コロンブスの話にフェルナンド2世はあまり興味を持たなかったが、イサベル1世は惹きつけられた。計画は、懺悔聴聞師のエルナンド・デ・タラベラ（フライ・エルナンド・デ・タラベーラ）神父を中心とする諮問委員会が設けられ、そこで評価されることになった。1486年だけで二度[注 14]委員会は開かれたが、コロンブスが示したアジアまでの距離が特に疑問視され、結論は持ち越された。

コロンブスはメディナセリ公の支援を受けながらコルドバの彼の城に滞在し、カトリック両王との面談を模索する一方で、交流を持った医師や学者らの中の一人から当時20歳（または21歳）の小作人の娘ベアトリス・エンリケス・デ・アラーナ（スペイン語版）と[20]恋愛関係となり、1488年8月15日にフェルナンド（スペイン語版）が生まれたが、コロンブスはベアトリスと正式に結婚しなかった。

しかしスペイン王室からの返事はなかなか届かなかった。コロンブスに好意を持った委員会長のタラベラや、メンバーの1人であるドミニコ会のディエゴ・デ・デサらは、委員会が否定的結論を出そうとすると引き延ばしにかかっていた[16][注 15]。コロンブスはポルトガルのジョアン2世に手紙を送ったが、バルトロメウ・ディアスの喜望峰発見もあって話がまとまることはなかった[注 16]。また、弟バルトロメをイギリスのヘンリー7世やフランスのシャルル8世の下に差し向け、計画の宣伝をさせた。いずれの王からも支持は得られなかったが、シャルル8世の姉アンヌ・ド・ボージューの歓待を得て、バルトロメはフォンテーヌブローの宮殿に数年間滞在した[21]。しかしこれらの行動も実を結ばなかった。

一方のスペイン王室は、1489年5月12日付でコロンブスが王室に謁見するときに必要な宿泊費を無料にする通達を出す[21]など、不完全ではあるが金銭的援助を行い[19]、決して彼を邪険にしていたわけではなかった。しかし1490年、タラベラの委員会は提案に反対する結論を出したことでコロンブスは諦め気味にパロスに戻り、ラ・ラビダ修道院に向かった。話を聞いたペレス院長はコロンブスを慰留し、イサベル1世の側近セバスチャン・ロドリゲスを頼り、王室に再検討を促した。このわずか2週間後、コロンブスのもとに王室の書簡が届き、旅金を添えて出頭するよう勧告する内容があった。