在上层贵族的引荐下，哥伦布终于获得了裘安王子的接见。当时，这个少年王子掌管航海权，手中也有一定的实力。于是，哥伦布开出了一个价格很高的报价单：要三艘大船、优秀的船员、足可以使用一年的费用，封给骑士头衔，还要在新发现的土地上担任总督，出海所得财富的1/10归哥伦布所有。
裘安王子是个很聪明的人。他对哥伦布的计划表示怀疑，对他开出的报价单也不满意，但是，并没有马上回绝他的要求，而是答应召开一个学者会议，对他的计划进行评审。如果学者们认为哥伦布的计划可行，就准备接受他的条件。然而，由于这些葡萄牙的学者在探险知识方面还不如航海者知道的多，所以，他们认为哥伦布的计划并不可行。学者们的意见，促使裘安王子拒绝了哥伦布的要求。葡萄牙王子的态度使哥伦布苦心经营的计划全部落空。他原以为，王子会为东方的黄金所吸引，因而，也必然会同意他的条件。现在，他不得不再想新的出海途径。
正当哥伦布为实现自己的理想而一筹莫展的时候，新的打击又降临到他的头上。他的爱妻，在重病之下不治而亡。哥伦布悲痛欲绝。妻子死了，也就等于失去了葡萄牙贵族的支持；没有了他们的支持，在葡萄牙不可能干成任何事情。他明白，在葡萄牙的努力全白费了。悲痛之余，哥伦布开始寻找新的出路。
在葡萄牙已经难成大事，哥伦布不得不把目光移向别的国家。这时，传来西班牙王国成立的消息。并且，新成立的西班牙王国正网罗出海探险人才。哥伦布听到这个消息，立即打点行装，前往西班牙寻求出路。
哥伦布东行来到西班牙。他虽然是满怀希望而来，但是，这里也没有鲜花和笑脸迎接他。哥伦布在这里举目无亲，没有钱财，没有靠山。他只好一面作工，一面寻找求见国王的机会。在哥伦布流浪期间，葡萄牙王国的裘安王子即位。他很想在航海探险方面超过他的前辈亨利王子。
这时，他又想起了哥伦布。当有人告诉他，哥伦布已经到了西班牙时，裘安急了，他怕这个难得的人才被西班牙利用，就秘密派人前往西班牙找到哥伦布，告诉他，国王答应他提出的一切条件，只要他愿意为葡萄牙出海探险。然而，哥伦布是个很有主见的人。他怀疑葡萄牙国王的诚意，就谢绝了葡萄牙的秘密使者。他决心在西班牙实现自己的目标。
为了生存，哥伦布就在港口找些活干。他干临时工的巴洛斯港在当时是个较大的港口城市。这里居住着一些学者、修士、有知识的僧侣。哥伦布主动结交这些人士，一有空闲，就向他们讲述自己的计划。渐渐地，有见识的僧侣对他的计划发生了兴趣。有人愿意出面为他引见王室成员。由于教会的活动，哥伦布终于有机会见到了王室成员，向他们介绍了自己的计划。可是，此时的西班牙统治者正忙于国内统一，内部政权尚未稳固，哪儿有心思到外面去掠夺？所以，哥伦布再次受挫。
哥伦布在西班牙碰壁之后并没有死心，又分别来到法国和英国，向这些国家的统治者介绍自己的如意计划。这些国家的王室成员，更不相信哥伦布，没有一个贵族或王子认真对待过他的计划。在这种情况下，哥伦布又无可奈何地返回西班牙。在这里，他至少可以找几个修士、僧侣，一起谈谈他的探险计划。有这样几个知音，也可暂时安抚一下他那屡屡受挫的自尊心。
熬过了几年的寂寞和无奈之后，哥伦布盼来了希望。西班牙国内获得了统一。统治者有意向外扩张。环境的稳定和哥伦布的努力，使他的计划引起了西班牙银行家的注意。银行家把哥伦布的计划说给王室的财政顾问。
财政顾问又把这个计划当作故事告诉喜爱财富的王后。王后又找机会说服国王。国王经过考虑后接见哥伦布。兜了一个大圈子，哥伦布终于可以向西班牙国王陈述自己的计划了。
哥伦布说服西班牙王室的工作进展缓慢。
当时，西班牙刚刚成为统一的国家，国王分别是斐迪南和伊萨白拉。原先，两人是各自国家的国王，他们结婚后使两国合并，统一的西班牙成为欧洲的强国之一。
两位国王第一次召见哥伦布时，认真听取了他的计划。讲究实际的斐迪南国王，最关心这次冒险可能带来的物质利益，他用怀疑的眼光望着哥伦布，问：“您冒这么大风险的目的究竟是什么？”哥伦布于是把计划的要点，向这位不见兔子不撒鹰的国王重复了一遍。
斐迪南国王听罢，摇摇头，说：“无论如何，在摩尔人（西班牙南部割据一方的异教徒）的威胁没有消除以前，我们还不能对您的计划给予帮助。“陛下，您打算放弃这个计划了？”哥伦布失望地问，“如果是这样，那么葡萄牙将会先于西班牙，捷足先登。”“我没有说过彻底放弃，我只想说时机还不成熟。”斐迪南国王回答。
女王伊萨白拉是个狂热的基督徒，她对哥伦布计划中的传教内容很感兴趣，就劝说国王成立一个专家委员会，研究哥伦布的航海计划，以便在适当时机采取行动。
斐迪南国王表示恩准。
但是，专家委员会却在无休止的争吵中把计划搁置下来，一拖就是4年。
哥伦布因为计划迟迟不能得到批准，心急如焚，度日如年。有一次，他甚至绝望地想到，“作为一个外国流浪汉，我也许注定要一无所成了。”这个念头当然不符合这位倔强的航海家的性格。
有一天，哥伦布为了宣泄自己的情绪，找到那位支持他的神父，忿忿地说：“只有您鼓励我，可您瞧瞧他们，他们嘲笑我是‘疯子’，把我拒之门外！”“您不要灰心，只有国王说了才算数。”神父开导他说。“那您让我怎么办？”“等待！”“等待！等待！那些人也总是这么说，可要我等到什么时候！”谈话就这样不欢而散。
在等待期间，哥伦布还把他的计划献给英王和德王，都没得到答复。他终于明白，目前，只有西班牙具备支持他的权力和力量，他除了继续等待之外，没有别的出路。
1489年5月，斐迪南国王和伊萨白拉女王，在和摩尔人作战的军营里再次召见了哥伦布。一年半以后，哥伦布又受到国王的第三次召见。虽然谈判没有成功，但事情终于有了转机。
1492年1月，摩尔人在西班牙的最后一个据点被攻占了。在和摩尔人的长期战争中，西班牙人耗费了大量的人力物力，一些大臣和贵族急于到海外去捞取金钱，也敦请国王支持哥伦布的计划，这才使国王下定了决心，要和哥伦布签订协议。
消息传来，人们都以为哥伦布一定会高兴得发疯了，没想到他只是“哼”了一声，说：“我终于战胜了所有的人，因为我是上帝指定的人。
派我把福音书带给东方的居民，这是上帝赋予我的使命。”在哥伦布看来，他的成功是自己赢得的，不是别人恩赐的。长期等待的痛苦不但没有消磨掉他的意志，反而使他变得更加自命不凡。
签字这一天，国王对哥伦布的接待非常隆重，在热烈的气氛中，一切障碍都消除了。
协议满足了哥伦布所提的要求，协议商定，哥伦布将以西班牙王室的名义，去寻找通向东方的航路，并且封他一个很大很长的“头衔”：“在各海洋中由他亲自发现或取得的一切岛屿及大陆的海军上将”。
协议签订以后，有位叫科斯塔的地理学家特意来迎接哥伦布，尽管他认为哥伦布的航海计划根本行不通，仍然来向哥伦布表示祝贺。
交谈中，阿科斯塔郑重地告诉哥伦布，说：“我认为您弄错了，您肯定到不了‘大汗’的国家。”“为什么呢？”哥伦布反问道。
“因为那块陆地比您想象的要遥远得多。”“如果我到达了那块陆地呢？”“那也不是‘大汗’的国家，而只能是一块新的大陆！”“噢，您真是不可思议，居然幻想出一块‘新大陆’来了！”两人究竟谁对谁错呢？只能等待哥伦布远航的结果了。既然协议已经签订，那么揭开这个谜底的日子将不会太久了。
远航的准备工作遇到了很多困难。首先是钱，为了凑钱，伊萨白拉女王把自己心爱的首饰都变卖了，这笔钱加上哥伦布到处募集来的捐款，再加上从国库支出的一部分，总算勉强凑够了数。
接着是找船，好不容易弄到三艘，其中有两艘是西班牙政府强制征用的，另一艘由宾松兄弟自愿提供。最大的一艘叫“圣玛丽亚”号，长111英尺，可以载重100吨，搭乘30至40名船员，另外两艘叫“品达”号和“尼纳”号，可以分别载重40至50吨，搭乘船员20名左右。
有了钱和船，只完成了准备工作的一少半，因为最重要的是要有人，需要有几十名豁得出命的真正水手，到哪儿去找呢？正当哥伦布为寻找伙伴发愁时，宾松兄弟中的哥哥马丁·宾松主动找上门来。起先，哥伦布并不信任他，一见面就试探着问他：“感谢您对我这次远航的支持，可是这很可能是一次徒劳无功的远航，弄不好，不但船回不来，连命都得搭上。”“唔，您真是这样想的吗？我可从来不认为结果会一无所获，既然我把自己的船都带来了，就没打算把它撇下，死活全拴在一起了。”马丁干脆地回答。
“这么说，您心甘情愿和我一块去冒险啰？”“我和您有共同的愿望，我请求与您合伙，同舟共济。”“妙极了。”哥伦布边说边在马丁的肩头重重的拍了一下。随后，马丁又把弟弟维森特介绍给哥伦布，当哥伦布了解到维森特的海上“功夫”后，立即对两兄弟说：“我现在就发布这次远航的第一道命令，‘圣玛丽亚’号担任旗舰，由我亲自指挥，马丁指挥‘品达’号，维森特指挥‘尼纳’号……”有了指挥官，水手就比较容易找了，很快就聚集了87个人，其中有不少是从监狱里提出来的罪犯，还有几个死囚犯。哥伦布挑选这些人，是因为他们大多数都有过当“海盗”的经历。
冒险生涯
1492年8月3日的帕洛斯港，哥伦布将从这启程前往未知的东方。
七年前，他带着儿子第一次到这儿时，他是一个流浪汉。如今，他是海军上将了，而且，他很快便会成为新发现的土地上的总督。
他将率领三艘船去探险。这些船已十分破旧。虽然人家答应资助他，但不是说他要什么就有什么。君主们、资产者们对每一个可能收不回的钱都是十分吝啬的。三艘船中，最大的圣玛利亚号约120吨，另两艘王牌号和少女号要小得多。
水手也是好不容易招募来的。地圆说尚不流行，海洋无底洞的说法仍有许多人相信。掉进无底洞，那就永远回不来了。于是在君主同意下，强迫征集了一批罪犯，才勉强凑足所需的水手。
尽管如此，海军上将还是十分兴奋。亲自率领探险船队到未知的远洋去使他激动万分，竟至彻夜不眠。当太阳的第一缕光线刚冲出地平线，把帕洛斯原野上空飘浮的白云染成玫瑰色时，他的挚友，拉比达修道院院长佩雷什就陪他登上了旗舰。
海员们拔起大锚，锈着十字架的帆开始鼓起来。前来送行的居民聚集在沙丘上呐喊着，充满支持、关切之情，也有的大声指责。拉比达的僧侣们跪着祈祷。船借着风力渐渐远去。
船队首先朝加那利群岛驶去。途中，王牌号坏了，不得不在加那利群岛停下来修理，同时又对少女号进行了改装。9月6日全体船员去做了弥撒，然后离开加那利，驶向茫茫的大洋。
头几天，风平浪静，阳光灿烂，水手们有的还跳下海去洗澡。为了稳定水手们情绪，哥伦布耍了个小花招。他在9月9日的航海日记中写道：“我们向前航行了60海里。我决定比实际走过的路少算一些里程，以免因航行太久而使我们的人丧失勇气。”9月14日，正当水手们的怨言渐渐多起来时，少女号上的人报告说看见了许多鸟。这是不是声明陆地已经不远了？葡萄牙人就是跟随鸟发现许多岛屿的。两天后，人们更为激动，到处可看到一绺一绺的草，像是刚刚从陆地漂过来。水手们以为陆地快到了，但一次次测定水深，几百米的长绳也够不着底，看不到接近大陆架的迹象。哥伦布内心明白，不可能这么快就到达陆地。他们其实是驶进了马尾藻海。它位于北大西洋环流中心，风浪很小，水流平缓，马尾藻便聚集在这里生长、繁殖，覆盖了大约450万平方公里的海面。
船只艰难地在“草原”上航行。有几天海风停息，船队几乎停滞不前。人们怨言四起，都说这个海洋是个怪物，连一丝风也没有，不然可以返回西班牙去。
船上的工作单调而乏味，特别是在15世纪的条件下。
在3时、7时、11时各有两人值班。当班者必须用海水洗甲板，既保持甲板干净，又防止木制甲板被太阳晒裂。其他的人做帆樯索具方面的工作。木工则填塞甲板上装酒和水的木桶。舵手处在船尾下的舵柄边，又闷热又憋气，只有处于船首或桅楼上陈望的人才高高在上，悠然自得。船首和船尾有一些挂在船舷外的台架，是专用于大小便的。交班前，还必须把底舱的脏水排掉，这些水带有废物和淹死的小虫，臭气熏天。一天只供应一次热饭菜，这时全体船员聚会在一起，用刀子割着木碗里硬邦邦的腌肉。