在西班牙等待宫廷对西航计划批复的五六年是哥伦布一生中不愿谈起的困窘日子。当他实现了伟大梦想，发现了“印度”以后，每当他回忆起那段岁月来，也难免黯然神伤，似乎心灵再次经历了痛苦的洗礼。伟大的人物大多有一颗敏感而自负的心，深信自己的远大抱负一定能实现，但经常遭到别人的挖苦讽刺，这让他那高傲的心十分难过。
执政者因为对摩尔人的战争，不断地从一个城市迁移到另一个城市：塞维利亚、圣卢卡尔、埃尔波多、科尔瓦多、萨拉曼卡、穆尔西亚、马拉加。哥伦布如同一叶浮萍，随着动荡的国家，长途跋涉，四处奔波，翻越崎岖的山岭，经历各种磨难。除了身体的劳累，更让这个高傲灵魂难堪的是他的经济已陷入困境，没有钱让他这样不断地长途“旅行”。
当时负责处理他的建议的专家委员会准备听取他的说明，而这很快就被军事上的一些事情所打断。他也会参加一些贵族们无意义的会议，不过是清谈着浪费时间。那些贵族的浮华生活及谈吐让哥伦布很是头疼。
在这种让人无奈的情况下，他决定寻找另外的援助人。1488年，他写信给葡萄牙国王约翰二世，请求他接见，发给他护照，保护他到里斯本的安全。其实在这之前，葡萄牙国王几次派密使到西班牙与哥伦布碰面，这也是他向葡萄牙申请援助的原因。第一次是在他前往圣玛利亚港的船厂了解快帆船的情况以后，在返回的路上，一个骑马人朝他疾驰而来，向他传达葡萄牙国王要他回去的旨意。第二次是在一周之后，这位密使又在拉比达的教堂里会见他。哥伦布对他的答复是，要国王亲笔写信来，他才能作出决定。这种秘密联系一直延续到1485年春夏之交，那位密使第三次来到科尔瓦多，带来了盖有葡萄牙国王印鉴和由国王亲笔签名的信件，保证将给他以朋友的待遇。他后来又收到了约翰二世1488年3月20日给他的信，邀请他回葡萄牙去，保证他不会有任何麻烦。在那封信中，葡萄牙国王称他为“克里斯托弗·哥伦布，我们的特殊朋友”；他还在信中说：“至于你因为这是件冒险的事，出于某种您所不得不考虑的原因而对我们的司法有所忧虑的话，我们可以通过此信向您保证，您可以来去自由。”但哥伦布最终没有接受葡萄牙国王的邀请，可能因为他十分了解这位国王暴戾严酷的性格：对他认定的敌人决不手下留情。他不敢贸然前往。这又让他那伟大的计划继续耽搁下去。
在此期间，为了维持生活，哥伦布在塞维利亚设立过一个“制图家兼书商哥伦布兄弟事务所”，经营制图和售书业务。
哥伦布能在西班牙这么长期待下去，也应归功于他在宫廷中的一些朋友。他经常得到迭戈·德德萨修士的帮助。此人是塞维利亚大主教，后来又担任宗教法庭总法官。在1487年间，哥伦布经常得到王室金库的接济和此人有很大的关系。哥伦布与德萨一道随同王室到了科尔瓦多。
在科尔瓦多期间，哥伦布为自己租了一间房子，房东是一个参加过对葡萄牙作战的老兵。他对哥伦布十分友好热情，经常为哥伦布准备美味可口的饭菜与美酒。科尔瓦多有一批热那亚侨民，他们常在一起聚会，哥伦布也去参加他们的活动。1486年，他在这里认识了迭戈·德·哈腊纳，并到他家里做客。在他家里，哥伦布认识了哈腊纳的堂妹贝特丽丝·恩丽克丝，姑娘只有二十来岁，身材娇小，相貌甜美可人。她是一个葡萄园主的孤女，没落贵族家庭出生，他们的住地距离很近，经常有见面和谈话的机会。通过谈话她知道了哥伦布那远大的抱负，同时对他现在所遭遇的窘境深表同情。爱情总是在同情中产生，两颗年轻的心因为相互的理解而碰撞出炽热的火花。贝特丽丝·恩丽克丝这个热情的少女让哥伦布漂泊的心有了安放之所。
其实哥伦布当时是有妻子的，而且和他的夫人费莉帕的关系也是融洽与和谐的。费莉帕对他的西航计划十分了解，并且也非常支持。在哥伦布埋头于书籍和地图的探索中时，她常常和他一起讨论，有时还帮助他查阅一些资料。但他们之间的婚姻总带了那么一点利益关系，即哥伦布与她结婚，从内心的深处来说是要进入上流社会与宫廷，借以实现他的抱负。但与贝特丽丝的关系则感情成分更多一些，虽然哥伦布当时年纪已近不惑，已经36岁。他们没有正式结婚，但他们相处甜蜜温馨，在各种流言蜚语的中伤中，竟没有破坏他内心的安宁。哥伦布在往来奔波时，曾经将贝特丽丝带到韦尔瓦去。她在那里同小迭戈和哥伦布前妻的两个姐妹在一起生活过一段时间。
1487年8月15日，贝特丽丝生下了费南多--哥伦布的第二个儿子。费南多长大成人后为哥伦布写了传记。哥伦布第一次远航归来后就与贝特丽丝·恩丽克丝分开了。有人就此事批评哥伦布不能算一个虔诚的天主教徒，因为天主教徒必须恪守基督教“十诫”，其中有一诫是不许奸淫，不能姘居，后来一些为他写传记的笃信宗教的作者也觉得此事难于下笔。哥伦布和贝特丽丝·恩丽克虽然断绝了关系，但一直提供金钱让她生活无忧。他在临终前的遗嘱里还把她托付给他的财产和封号的继承人——大儿子迭戈，要他好好对待她。他在遗嘱里写道：“贝特丽丝·恩丽克丝是我儿子费南多的母亲，应该升格使其与她的地位相称，以便让她过上富足并受人尊重的生活。因为我在许多方面亏待了她，我这样做是为了从我心上卸下沉重的包袱，使良心得到安宁。心灵的愧疚使我痛苦不堪。”哥伦布还一直把费南多和与前妻合法婚姻生的儿子迭戈同等对待。