1486年1月，哥伦布自韦尔瓦（Huelva）的帕洛斯港踏上西班牙国土，他完全没有料到，他从这里起航去寻找印度，要等到六年之后。

上岸当天，哥伦布走进拉比达修道院（La Rabida Monastery），与方济会（Franciscan Order）的灰衣修士会面，托他们把西航计划送往王室枢密院。所以，哥伦布把这个日子视为他效力西班牙的开始。为了保险起见，他在葡萄牙护照上加注了方济会的签证，然后上路去塞维利亚（Sevilla）。

伊莎贝拉一世是军队总管，当时住在塞维利亚，斐迪南二世也从前线回来和王后一起过冬。哥伦布没有马上求见双王，而是先去拜访西班牙最富有的梅迪纳-西多尼亚公爵（Duques de Medina-Sidonia），他实际统治着塞维利亚南侧的桑卢卡尔港（Sanlucar），只要他愿意，他自己就可以担负远航的一切费用。遗憾的是，这位公爵没兴趣。哥伦布又去找梅迪纳塞利公爵（Duques de Medinaceli），这位公爵原本也是王位继承人，甚至有权认为伊莎贝拉一世是篡位者，夺去了原本属于他的王位，但他不仅没去争夺王位，而且是最忠诚于双王的王公。他喜欢哥伦布的计划，下令保护哥伦布并提供给他食宿，而且还要在自己的港口船坞给他建造三桅帆船。

开春后，斐迪南二世和他的骑兵移师科尔多瓦大本营，按照他的命令，大封建主们已经率领各自的军队整装待发，准备发动春季攻势。梅迪纳塞利公爵也将参加这次战斗，所以他无暇顾及哥伦布，只好把他引荐给塞维利亚大主教门多萨（Pedro Mendoza）。此人相当于总理，拥有“第三国王”的别称，后来是西班牙红衣主教，接近这个人，几乎等于接近了双王。另外，公爵给双王写信，推荐哥伦布，双王回信说，请把哥伦布送到科尔多瓦。

5月初，双王第一次召见哥伦布。此时，伊莎贝拉一世35岁，斐迪南二世和哥伦布同为34岁。哥伦布让双王看他弄到的世界地图，让他俩产生了想探索那些未知土地究竟在哪里的愿望。要知道，哥伦布是在世界霸权分配明显利于葡萄牙的背景下从葡萄牙跑过来向西班牙献计的，双王被他特有的热忱打动了。但他俩确实无暇顾及，驱逐穆斯林的战斗迫在眉睫，于是他俩授权远在萨拉曼卡省（Salamanca）的专家委员会，让他们研究给哥伦布的西行方案。15日，斐迪南二世离开科尔多瓦去前线。

哥伦布遵照双王指示，去见王室总会计师金塔尼利亚（Alonso Quintanilha），他口若悬河地展望西航奇迹和可能带回的金银和宝石，让总会计师垂涎三尺。总会计师非常同情哥伦布的窘困，下令给他提供吃的、用的。

至于萨拉曼卡专家委员会，中国人编造了许多不实的段子。比如说，有一位委员问哥伦布，即使地球是圆的，向西航行可以到达东方，但回港时，必然要从地球下面往上爬坡，可帆船怎么可能爬上来。这是不可能的。主持委员会工作的是塔拉维拉修士（Hernando de Tallavera），他是伊莎贝拉一世无私的万能大臣，也是她的忏悔牧师，是一位博学的圣人。萨拉曼卡省有萨拉曼卡大学，大学执政马尔多纳博士（Maldona）是委员会的成员，大学里还有最伟大的犹太天文学家萨库托（Abraham Zacuto）。这些人是不可能犯这种低级错误的。哥伦布之所以没有得到委员会的认可，是因为他始终不愿透露托斯卡内利的那些地图信息，也没提及托斯卡内利，他非常害怕委员会问起这些信息是怎么来的。所以他像对待双王一样，只是引证一些无关紧要的空洞理由让大家相信他的计划是可行的，却闭口不谈关键依据。塔拉维拉是一个清澈透明的人，对哥伦布这种不爽快的态度非常反感。其他委员也一样，对这位理由不充足、没有地图规划，却又刚愎自用的外国人，一致感到不耐烦，甚至很生气。(www.daowen.com)

哥伦布太不顺了，所有人都把注意力放在了格拉纳达圣战上，很少有人注意他。事情拖到秋天，整个安达卢西亚区（Andalucia）又遭受了大水灾，大家又忙于抗洪救灾。冬天，双王本可以利用歇战亲自过问此事，但安达卢西亚气候恶劣，双王北上去托莱多（Toledo）过冬。此时，双王的财源彻底枯竭了，他俩把自己的所有财产全用完了，所以非常感谢及时捐献财力的封建领主。哥伦布的远航完全成了泡影。

不过，王室在最困难的时候也没有彻底放弃哥伦布，1487年5月5日，双王送给哥伦布3000马拉维迪，7月3日又给了他3000马拉维迪。8月18日，在梅迪纳-西多尼亚公爵的大力援助下，迂回格拉纳达西侧的斐迪南二世夺回马拉加城（Malaga），然后把王室搬了过去。27日，双王送给哥伦布4000马拉维迪，让他当作去马拉加城的旅费。不过历史文献没有记载哥伦布到底去没去见国王。

哥伦布动摇了，他心灰意冷，常去19岁的犹太少女恩里克斯（Henriquez）那里寻求温暖，继而他给葡王写信，愿返回里斯本，重新为他效力。1488年3月20日，若昂二世给哥伦布回信：“您可以来去自由，决不会因任何民事原因或其他性质的罪名而受到逮捕、拘留、控告、传讯、起诉。”哥伦布收到葡王的回信，获悉若昂二世愿意热情补偿他。不过哥伦布冷静地想了想，葡王大航海政策是垄断性的，对任何航海资料全都是绝对保密的，他非常担忧葡王如果知道了他窃取托斯卡内利的信和地图，会如何处置他。所以最终，哥伦布没回葡萄牙。

哥伦布到死也没和恩里克斯结婚，但是8月15日，他俩的私生子诞生了，哥伦布用西班牙最高贵的国王斐迪南的名字给孩子起名。国王也算对得起他，他们再次传令：“我们各个王国和领地的所有城镇乡和地方的政府、司法机关、市镇议员、骑士、绅士、官员、名门望族，哥伦布投奔了我们的宫廷，他懂得一些对我们有用的事情，不管他到你们谁那里，都要接待他，并安排好住宿。不过，他的随从无钱不能住店。”

1490年，葡王派专门使者来见西班牙双王，为太子阿方索向伊莎贝拉公主求婚。5月，西班牙为这对恋人举行前所未有的豪华订婚礼。11月，公主在一大群西葡权贵陪同下前往里斯本。在这段大喜大庆的日子，哥伦布却很痛苦，他等待专家委员会的意见等了四年，结果竟是否定的。双王依然没有做出彻底放弃的决定，但仍以战事为理由暂时拒绝了他。

此时，哥伦布的大儿子迪亚哥11岁，在韦尔瓦的姨妈家。他的私生子斐迪南两岁，和他的情妇在科尔多瓦。哥伦布缺少供养他们的必需品，他再一次感到走投无路。