このころ、コロンブスは積極的にスペイン語やラテン語などの言語や天文学・地理、そして航海術の習得に努めた。仕事の拠点であるリスボンでパオロ・ダル・ポッツォ・トスカネッリと知り合う機会を得て、手紙の交換をしている。当時はすでに地球球体説は一般に信じられていたが、トスカネッリはマルコ・ポーロの考えを取り入れ、大西洋を挟んだヨーロッパとアジアの距離はプトレマイオスの試算よりもずっと短いと主張していた。『東方見聞録』にある黄金の国・ジパングに惹かれていたコロンブスはここに西廻りでアジアに向かう計画に現実性を見出した。また、現存する最古の地球儀を作ったマルティン・ベハイムとも交流を持ち意見を交換した説もある[13][2- 1]。これらの収集情報や考察を経てコロンブスは西廻り航海が可能だとする5つの理論根拠を構築した。ラス・カサス『インディアス史』（第5章）に記載されたその内容は、[14]
地球は球体であり、西に進めば東端にたどりつく。

地球の未知の部分はアジア東端からベルデ岬諸島以西だけになった。

2世紀のギリシア人地理学者のマリヌスはヨーロッパからアジアまでは地球の15/24に当たるという。したがって未知の領域は9/24=約1/3となる。

マリヌスが認識していたアジアは（当時認識されていたという意味で）現在のアジア東端までに比べれば狭い。したがって未知の領域はさらに狭くなる。

9世紀のイスラム人天文学者アルフラガヌスは経度1度=約56.6マイルと計算した。したがって未知の領域は56.6×360/3=約6,800マイル。しかもこれは赤道上であり北寄航路ならば距離はさらに縮まる。

この考えの根底にはアリストテレスの地理観を引き継いだ中世キリスト教の普遍史観から、世界はヨーロッパ・アジア・アフリカの3大陸で成り立っていたという概念がある。地球の大きさについても、北緯28度におけるカナリア諸島から日本までを実際の10,600海里に対しコロンブスは2,400海里と、非常に小さく見積もっていた[15]。
王室への提案

1484年末[注 10]、コロンブスはポルトガル王ジョアン2世に航海のための援助を求め、その自信に溢れた弁舌に[2- 2]、ジョアン2世は興味をそそられた[16]。コロンブスは資金援助に加え成功報酬も求めたが、高い地位や権利、そして収益の10%という大きなものだった[注 11]。王室は数学委員会（フンタ・ドス・マテマティコス）の諮問にかけて検討したが、回答は否決だった。コロンブス以前にも大西洋への航海は何度か試みられたがすべて失敗し、一方でアフリカ探検はディオゴ・カンがコンゴ王国との接触に成功し[16]喜望峰に達する寸前まで来ていたこと、さらにコロンブスの要求があまりに過剰だと受け止められたことも影響した[17]。

再度コロンブスは提案を上奏したが決定は覆らず[17]、ジョアン2世はコロンブスが自費で航海をするならばよいと言うのみだったが、コロンブスにはそのような資金がなく[16]、借金さえ抱えていた[6]。このころ、コロンブスは妻フェリパを亡くし、1485年半ばごろ、8年間過ごしたポルトガルに別れを告げる決心をつけた[6]。
スペイン時代

コロンブスはリスボンから海路、スペインのパロスに着き、そこからウエルバのティント川沿いの丘に建つラ・ラビダ修道院を訪ねた[注 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]。