只要我们能把希望的大陆牢牢地装在心中，风浪就一定会被我们战胜。
——哥伦布
（一）
在葡萄牙未能受到实现梦想，哥伦布再次来到西班牙，因为他对行动迟缓的塔拉维拉委员会还抱着一丝希望。他的弟弟巴托洛梅也结束了自己的制图业务，开始一次长途旅行，试图向欧洲其他国家的某些国王兜售哥伦布的西航计划。
巴托洛梅首先从里斯本到达英国，希望能说服海因里希七世支持哥伦布的西航计划，但未能打动国王。两年后，他又到了法国，求助于查理八世。在法国，他获得了国王的妹妹安娜·德·贝奥热的好感和同情。在贝奥热的介绍下，巴托洛梅与法国国王建立了密切的关系，但对于横渡大西洋的计划，国王却没有给出任何支持的表示。
在西班牙等待期间哥伦布是如何生活的，我们不得而知。1489年5月，伊莎贝拉女王再次召见了他，但召见的结果却无人知晓。据记载，不久后哥伦布便作为志愿人员加入了包围摩尔人城堡巴札的军队中，并且“表现得十分勇敢，这与他的智慧和崇高的目标相配”。
直到1490年底，特拉维拉调查委员会才给出自己的报告，但报告的结论却是否定的。参加审查哥伦布计划的委员们报告伊莎贝拉女王，称从西向东横渡大西洋的计划“基础是不稳固的”，它设想的利益“在任何一个有教养的人看来都是不可靠和难以办到的”；建议的到亚洲的航行，即使船只能够回来也需要3年的时间，而能不能回来他们认为也是值得怀疑的；大西洋比哥伦布想象得辽阔得多，有许多地方要航行都是不可能的。
因此，在调查报告的最后指出：对于一个没人住而又有真正价值的地方，上帝竟然会向他的子民隐瞒这么多个世纪，这是不可思议的。
委员会对哥伦布西航计划的批驳十分坚决，但我们也应该承认，委员会所有论点中除最后一点外，其余都是很有道理的。使用当时制造的船只，即使船长和水手都十分勇敢坚定，即使他们都善于节约粮食，恐怕也没有哪只船能够航行上万英里，从西班牙到达日本，再从日本返回原地。
哥伦布的计划再次陷入僵局。他很清楚，要想实现自己的计划，就需要重新找到出路。而在当时的情况下，只有女王同意，他才能产生新的希望。伊莎贝拉女王曾向哥伦布表示过：在征服摩尔人的战争结束后，他可以再一次提出申请。
于是，哥伦布差不多又等了一年。这时，他的弟弟巴托洛梅来信让他去法国，希望能一起舒服法国国王，实现他的西航计划。
见在西班牙始终没有消息，哥伦布决定接受弟弟的建议。在动身前，他来到帕洛斯，想同儿子迭戈和一直照顾迭戈的德拉·拉比达修道院牧师德·马奇纳告别。在这里，修道院院长胡安·佩雷斯神父劝哥伦布再一次找女王碰碰运气。
在佩雷斯神父的鼓励下，哥伦布再次给女王写了一封信。1491年7月，哥伦布终于收到了来自圣菲——在包围格拉纳达近郊最有一个摩尔人城堡期间建立的阵地——的女王的召见通知书。同时，伊莎贝拉女王还捎给哥伦布一批丰厚的礼物，其中包括一套相当讲究的衣服和一匹健壮的骡子。
1491年12月，哥伦布再一次出现在国王和女王面前。由于军队正在围攻格拉纳达，国王和女王的行宫就设在圣菲筑有坚固工事的营房里。
因屡次受到轻蔑对待而忧愤，且对西班牙的拖延政策也感到气愤，又对法国的支持充满希望，哥伦布第一次在国王和女王面前公布了自己的条件：要求提升为世袭贵族；封为新发现陆地的副王和总督；任命其为“海洋统帅”（大西洋是当时已知的最大的海洋，当时欧洲人对大西洋的存在还毫无所知）；有权从获得的财富中提取八分之一和从王室在印度的企业和机构的销售额中提取十分之一；与管理那里的主管机关有共同发言权；一切头衔和权利都世袭后代。
而且，这次哥伦布的态度非常坚决，表示如果国王和女王不能答应他的全部要求，那他们之间就不需要继续谈判了。
费迪南国王和伊莎贝拉女王一言不发地听着哥伦布提出的那些他们难以答应的要求。最后，国王夫妇告诉哥伦布，他的计划最后被驳回，他们对海外冒险没有兴趣——站在权利顶峰的费迪南和伊莎贝拉对这位热那亚人追求副王的愿望简直不能理解。
于是，哥伦布再一次失败了。
（二）
1492年1月，西班牙拿下了格拉纳达，费迪南国王和伊莎贝拉女王宣布不再接见哥伦布。他们认为，至少费迪南认为，这是他们最后一次接见哥伦布。
再一次受挫，哥伦布只好骑着他的骡子，把地图和仪器一齐装入驮包里，由他忠实的朋友胡安·佩雷斯陪伴着前往塞维利亚。他打算从那里由水路前往法国，与弟弟巴托洛梅会合，然后两人一起去向法国国王查理八世重新争取。
就在哥伦布离开圣菲这天，费迪南的王室司库路易斯·德·桑坦赫尔觐见女王伊莎贝拉，劝她接受哥伦布的条件。这位司库指出，哥伦布的远征费用不超过她的丈夫一个礼拜的招待费用。如果王室不愿意出这笔钱，他本人愿意为哥伦布筹措这笔经费。
至于爵位和报酬，哥伦布也只是说远航成功后，他才请求国王保证论功行赏。如果他果真远航成功，那么比起他所发现的新岛屿和发现到印度的新航路来，这些爵位和报酬简直就是微不足道的。
也许伊莎贝拉女王早就有意支援哥伦布，所以当路易斯·德·桑坦赫尔说完后，她欣然接受了他的意见，抓住了这个真正的最后机会。女王甚至提出要将王室的珠宝拿出来作为这项远航的费用，但桑坦赫尔认为完全没必要这样做。
于是，伊莎贝拉女王马上派出急使，在距离圣菲4英里的一个小村子里截住了哥伦布，将他叫了回来。
虽然伊莎贝拉女王改变了主意，表示愿意支持哥伦布的西航计划，但直到1492年4月下旬，哥伦布才与国王签订了协议书（通常称为这个协议书为《圣菲投降书》）。
协议书承认了哥伦布的所有要求，并由费迪南国王和伊莎贝拉女王按照西班牙的风俗，隆重地在协议书上签上“YoE/Rey”（我是国王）和“YoLaReyna”（我是女王）几个字。
费迪南国王还颁发给哥伦布一张护照，护照言简意赅地用拉丁文写成，里面称国王已经派哥伦布率领3艘轻快帆船开往印度地区。同时，还颁给他国书，国书一式三份：一份给“大汗”（中国皇帝），另外两份是空白的，准备在到达某个国家时，按照当地的国王头衔名填写。
在这份协议书的基础上，4月30日，王室又制订了法律证书。这份新文件，是由国王的秘书胡安·德·哥伦马撰写的。文件中称：发现者重新仅仅被称为“克里斯托弗·哥伦布”；他将去发现依然还未发现的“某些岛屿和陆地”；他“希望在上帝的帮助下将会发现和挣来”的这些地方；那些头衔，包括其他特权，也不言而喻地被推迟到“在发现和挣来上述大洋海的岛屿和陆地或这些地方以外的任何地方之后”再授予。
在文件签订后，哥伦布满怀希望地于5月12日离开了格拉纳达。
（三）
1492年5月22日，克里斯托弗·哥伦布作为由他提出的一切特权的所有者，从格拉纳达抵达了弗龙特拉的帕洛斯港，准备将这里作为自己的出海港。
之所以要选择这个小港口有几个原因。首先，哥伦布和本地最大的船主以及最有经验的船长宾松家族关系密切，所以在这里寻找船舶和海员都比较容易；其次，帕洛斯市的市政工作方面曾犯过一些错误，国王费迪南和女王伊莎贝拉便责成师长们“鉴于你们的失误给我们造成的损失”要进行忏悔，因此要求这里拿出两条装备良好的轻快帆船作为处罚。
1492年5月23日，哥伦布和他的朋友——修道士胡安·佩雷斯出现在帕洛斯港的圣·乔治教堂。就在这个地方，公证员宣布了国王的命令：要在10天之内将两艘轻快的帆船作好一切准备，两船的全体船员也要在这个期间内征集齐备，被给他们预付了4个月的工资。
10天的时间显然是有些荒谬的。在出海前，哥伦布整整准备了3个月。最终出海时，给哥伦布使用的轻快帆船不是两条，而是三条。因为碰巧在此期间有一条来自加利西亚的帆船停泊在帕洛斯港，哥伦布租下了这条船，作为自己的指挥船。
这条船名叫“圣·玛利亚”号，是哥伦布的船队中最为出色的一条轻快帆船。那时候，西班牙的船舶都有两个名字：一个是正式名称，前面照例都有一个“圣”字；另一个是诨名，是海员们常用的。“圣·玛利亚”号的诨名叫做“拉·加莱加”号，也就是后来我们常称的“加利西亚”号。
原本属于帕洛斯市的两条轻快帆船，一条名叫“圣·克拉列”号，但它的诨名“尼娜”号更为着名。之所以取这个诨名，是因为它原属于帕洛斯的尼娜家所有。
还有一条轻快帆船名叫“平塔”号，比“尼娜”号要稍大一些，是一艘轻巧伶俐的快速帆船。哥伦布的海员们从它的甲板上首先看到了新大陆，它也首先从新大陆返回祖国西班牙。
三条快速帆船都是把石头作为稳船物。船的构架零件、部件等，都是用木钉、木销连接起来的。这种木钉在美国的古老房屋构架中还能看到。
船身的吃水线上的外壳涂上了鲜艳的油漆，吃水线下面也涂了油漆，这样做可望防止贝类软体动物破坏船底。
风帆上面画了十字架和文章图案，每条船在进出港口时都要悬挂彩旗。女王伊莎贝拉在御旗挂在主桅杆上，迎风飘扬。御旗上面画着两座卡斯蒂尔城堡和两头莱昂狮子，按旗面四等分，交错排列。在船首前桅和后桅上，挂着远征探险队队旗。队旗是白底上缀着绿色的十字架，十字架端画着一个王冕，表示所到之处都要向阿拉贡国王退让。
三条船上还都安装了小型的原始大炮，以反击海盗和防止其他意外事件发生。但它们决不是军舰，因为船上既没有炮手，也没有士兵。
除了快速帆船的装备外，哥伦布还要招募海员，这对他来说是件比较困难的事。虽然费迪南国王和伊莎贝拉女王向所有的罪犯保证，只要他们参加哥伦布的远航，就赦免他们的罪行，但到处都在流传着这样的谣言，说这个热那亚人同一群乌合之众——“一群恶棍”去航行。
幸好有帕洛斯市的宾松、尼尼拉、金泰罗这三个主要航运世家的热心支持，哥伦布才找到了随他一起西行的海员。在海员中间，只有3位意大利人和一位葡萄牙人，其余的几乎全部都是出生在安达卢西亚的与宾松等几个家族有亲缘关系或熟悉的海员。
在三条船中，马丁·阿隆索·宾松指挥“平塔”号，他的弟弟弗朗西斯科任领航员（相当于副船长或大副）；他的另一个弟弟维森特·亚涅斯·宾松负责指挥“尼娜”号，这条船的船主和领航员是胡安·尼尼约。“圣·玛利亚”号是指挥船，由哥伦布负责指挥，也由他担任船长。这艘船的舵手由胡安·尼尼约的弟弟佩拉隆索·尼尼约担任。
每艘船上都有医师和舵手，舵手负责指点航向和航程。船队还有几个专门的人才，一个是路易斯·德·托雷斯，他是受过洗礼的犹太人，懂阿拉伯语。大家认为，他懂得阿拉伯语将来可以与中国人和日本人通话。第二个是罗德里果·德·埃斯科贝多德，他是船队的秘书，负责正式记录所发现的地方和人物。第三个是罗德利果·桑切斯，是国王的稽核官，他的主要职责是为国王获得应得的一部分黄金。还有一个就是迭戈·德·哈兰纳，是哥伦布继配的堂兄弟，出任船队的总管。
在三艘船上，“圣·玛利亚”号上共有39名船员，“平塔”号上共有26名，“尼娜”号上共有22名。除此之外，还可能有其他的两三人。这样一来，就使得参加远征探险队的总人数达到了90人。
这些人为了争得荣誉、黄金和猎奇探险，打破害怕新事物的习惯，毅然向大洋大海走去。虽说荣誉和黄金只有那些在远征途中幸免遇难、能活着回来的人才能拿到手，但命运却使他们参加了人类历史上最伟大的一次探险航行——哥伦布的首次远洋航行。