困难重重哥伦布虽有远大的抱负，但缺乏实现抱负的手段。他没有钱去造船只、招聘水手，除了借助王室的力量之外，别无它法。1484年，他正式向葡萄牙国王约翰二世建议，请求为他装备船队，西去东方。结果，他的计划被否决了。带着失望的心情，哥伦布辗转来到了西班牙的巴罗斯城，在那里得到了约翰·佩雷斯神父的热诚支持，把他引荐到王宫。1486年5月，伊萨白拉王后第一次召见哥伦布。哥伦布的忠厚、自信及丰富的地理知识给国王和王后留下深刻的印象，他们决定将计划交给专家委员会审查。然而，交出的计划如石沉大海，杳无回音。再次受挫，哥伦布心情非常沮丧。他通过弟弟把计划呈送给英国和法国国王，也没有得到理解和支持。无奈，1488年，哥伦布再次向葡萄牙国王请求支持，恰逢航海家迪亚士从非洲最南端好望角凯旋而归，国王对哥伦布的别出心裁的计划失去了兴趣。在葡萄牙彻底失望后，他只好再回到西班牙寻求支持。1490年，审查了四年的计划被否决了，不过，伊萨白拉王后的态度使哥伦布仍存一线希望。哥伦布又几次奏请了他的计划，虽没成功，但也没有气馁。1492年，再次奏请西航计划的哥伦布，在谈判破裂后，背起行囊，准备前往法国时，国王的财政大臣圣坦尼尔谒见了伊萨白拉王后，陈述了资助哥伦布计划的重要性。王后动心了，立即派急使追回了哥伦布。至此，8年的艰辛游说，终于使他如愿以偿了。1492年，他与国王签订了协定，规定：委任他为一切新发现海岛和大陆的司令，封他为被发现和夺得的海岛的副王和首席执政者；有权占有夺取财产的1/10；一切封号和权力具有继承权。
这项工作一开始就不顺利。因为女王虽同意了他的计划，但对远航能否成功，缺乏信心，不肯花大本钱去冒险，所以只给了他三条破军舰去碰碰运气。最大的“圣马利亚号”不过130吨，“平特号”90吨，“宁雅号”才50吨。成功了，一本万利；失败了，算白送他。
招募水手，也是件相当困难的事。因为当时“地圆说”尚不流行，而海洋无底洞的说法倒流传很广。所以，很少有人愿冒生命危险前去远航。要是掉进无底洞去，那就永远也回不来了。再说，茫茫大海，风急浪高，遥遥无期的枯燥而乏味的远航生活，说不定还有被大海吞没或被妖怪吃掉的可能，谁肯去受这样的痛苦和折磨！哥伦布没有办法，只得建议国王和女王，强迫征集了一批刑事罪犯，勉强拼凑了一个包括医生、翻译、秘书、王室全权监督、国王公证人、船队总管、舵手、船长在内的87人的探险队，并备足够一年的食物及西方文明的产物——原始小型大炮、帽子、花衬衫、镜子等。历时三个多月，终于万事俱备。
危机四伏的首航“新大陆”
1492年8月3日拂晓，西班牙巴罗士港人群熙攘，人们前来为哥伦布的舰队送行。哥伦布精神焕发，在卫队的护送下，登上了旗舰“圣马利亚号”，升起了西班牙国旗。他下令：“以上帝的名义，出发！”三艘船缓缓离开码头。无可奈何的水手们，对送行者挥泪告别。他们感到自己是向着黑暗的大地边缘驶去，向着那可怕的海洋无底洞走去，再无生还的希望了。此时的哥伦布心情也不平静，他深知大西洋的浪涛是何等的危险，但更为现在能成为掌握自己命运的主人而庆幸。他感到面前已无任何敌人，只有未知的海洋和世界在等待着他。按照计划，舰队朝加那利群岛驶去。
不幸的是，“平特号”出师不利，船舵一再松脱，船舱漏水，最后不得不停航检修。他们在加那利群岛补充了淡水、食物等，于9月6日，启航驶入了危险四伏、无人知悉的茫茫大西洋海域。
头几天，航行得比较顺利。天朗气清，静谧而湛蓝的海洋，既无吃人的海怪，也不见半点无底洞的影子，却有海鸥在船边飞翔，鱼儿在水中游戏。看来海洋也没什么可怕呀！水手们渐渐打消了对海洋的恐惧和疑虑。
然而，日子一天天过去，船员们感到海上生活的单调与枯燥：从晨课到晚祷，每隔半小时，根据沙漏(古代一种计时工具)报时一次，每四小时换班一次，日复一日地重复着。后面的加那利群岛已不见踪影，前面是无穷无尽的海面，水天一色，根本不见陆地的影子。人们的心里不免又开始恐惧起来。9月16日，突然在远方出现了一片草地，很像是陆地，大家兴奋起来，哥伦布还以为这么快就到了亚洲东部，更是格外高兴。可是，当舰队驶近时，人们大失所望，因为它根本不是什么陆地，而是浮在水面上的海草。更让人焦急的是，用测深锤测量海深，几百米长的绳子也触不到海底，说明附近很少有存在陆地的可能。而且，海草一望无际，好像茫茫的海上大草原。舰队艰难地在草原上航行，几天几夜都看不到头。
“会不会出什么事？”连哥伦布心理都焦虑起来，但他仍装做非常冷静。船员们开始忍受不住了，牢骚、怨言随时随处可以听见。整整在海草区航行了三周，才摆脱了恼人的纠缠。后来才知道，这是大西洋环流中心，覆盖了大约450万平方千米海面的“马尾藻海”域。
渡过藻海，前面仍是波涛汹涌、水天相连的海洋。突然，在一天的傍晚，一个水手惊呼看见了陆地，人们欣喜万分。然而，次日的事实告诉他们，所见的“陆地”不过是海市蜃楼罢了。他们生活在与世隔绝的环境里，生活的艰苦是不言而喻的。每天只中午供一次热饭菜，面包已发霉长满虫子，衣服也因汗浸、水淋而结成硬块。加上眼前那空荡荡、白茫茫的洋面，使充满恐惧的船员们忍受不了，不满的情绪再次发生了。他们强烈要求哥伦布改变航向，驶回西班牙，否则就把他扔到大海里去。
为了应付这场即将来临的“风暴”，哥伦布彻夜不眠，以最大的耐心劝说他们。他说，现在离家乡很远了，回去也有困难，离目的地倒越来越近，并答应发给大家一些钱，再坚持几天。这样才勉强把船员的情绪安定下来。
但不管遇到什么困难，哥伦布却总是一丝不苟地坚持把气温、海流的方向、流速的变化、罗盘针的偏差和鸟儿的飞行情况等记录在《航海日志》里，并绘制了海图。抱怨声也没有动摇他西航的信念，在日志中他写道：“一旦决定要抵达印度，就会继续航行下去，直到我们在上帝的帮助下找到印度。”正是这种勇于探险的大无畏精神和顽强的意志品格，才引导着船员们达到希望的目的地。
风助船行，10月11日，船员们看到海浪漂来了一根有树叶的枝条、一根开满花朵的树枝。哥伦布连忙对大家说，这是附近有陆地的迹象。大家听了，异常的兴奋，眼巴巴地盯着前方，仔细地搜索。大约晚上10点钟，哥伦布隐约望见地平线上有一个微弱的光点在闪烁，但他不敢肯定这是幻觉，还是陆地上的火光。次日凌晨两点，“平特号”上的水手突然大喊：“陆地！陆地！”平松舰长按事先约定的信号放了一炮。炮声划破夜空，惊动了整个舰队，个个欢天喜地，他们互相拥抱着，亲吻着。所有的人都在晨曦中瞧见了那块陆地。历时36天的大西洋航行终于结束了。
指鹿为马舰队迫近海岛，等待天明登陆。10月12日，阳光灿烂。哥伦布、平松兄弟两位舰长、公证人、监察官等人分乘3只小船，登上了海岛。一踏上海岸，身材魁伟的哥伦布身着暗红色海军上将制服，以海军上将、总督、这块陆地和未来发现的陆地的最高执政者的身份在海岸上升起了绿色的分别代表国王和女王的“F”和“Y”字旗，并签署了文件，正式以西班牙国王的名义占领了这个岛屿，并取名为“圣萨尔瓦多”(西班牙语“救世主”之意)。哥伦布环顾四周，想着自己幸运的未来，脚下的这块土地，就是幸运的开端，象征着救世主对自己的恩典。
岛上的居民好奇地瞧着这些不速之客的到来，起初，曾害怕地躲进森林，不过很快受到了红帽子、玻璃珠之类的引诱而出来了。他们赤身裸体，体型匀称，身体健壮，头发很粗，皮肤不黑也不白。他们没有武器，也不懂什么是武器。他们把这些白皮肤的人视为天外使者，是呼风唤雨的神所创造的奇迹。他们以友好的态度迎接这些“天外使者”，送给他们鹦鹉、棉纱等物品，并给船队送来了食物和淡水。这时，哥伦布一行对岛上居民还算友好，送给他们红帽子、铜铃等小物品。
哥伦布的目的是寻找出产黄金、宝石和香料的中国和印度。当他在岛上见到一些居民鼻子上穿挂着金片时，真有说不出的高兴。他想，他已来到中国土地了，不久就可满载奇异珍宝和黄金返回西班牙了。可当他在岛上走了一圈后，心里疑惑起来。因为马可·波罗描写的高大的中国宫殿、黄金遍地的地方并未出现，见到的只是一些小小的村落。然而，当他瞧见远处隐约还有许多岛屿时，疑惑顿时消失了。他猜想：这个地方也许不属于中国，马可·波罗不是说印度附近有许多岛屿吗？对，这就是印度群岛。打从这时起，他就一直指鹿为马，把这一带的岛屿叫做“印度群岛”，把岛上的居民叫做“印第安人”。其实，这是大西洋西岸、中美洲东岸的一群岛屿，离印度还远着呢！他初见的“圣萨尔瓦多”岛是今天巴哈马群岛中的华特林岛。巴哈马群岛由14个大岛、约3000个小岛和珊瑚礁组成，面积13950平方千米。
哥伦布兴致勃勃地率领舰队在“印度群岛”中航行着，发现了许多新岛，但未能找到黄金。不过，两个星期的航行，他们首次尝到了白薯、玉米的鲜味。哥伦布详细地记录了所见到的动植物群落。这些植物开着奇花，结着异果。鱼的种类繁多，并具有了世界上最奇妙的配色蓝、黄、红，真是美不胜收。哥伦布和他的同伴们在这里采集了几十种动植物标本。
舰队还在航行着，哥伦布一刻也没有怀疑过“他们离那金碧辉煌的宫殿很近了”。根据印第安人的传闻，船队向西南航行。10月28日，一个巨大的岛屿果真出现了。万紫千红的花园、青翠欲滴的树林使他们心旷神怡。哥伦布说这是他所见到的最美丽的岛屿。哥伦布满怀希望地在岛上寻找出产黄金的地方，他拿出少量黄金，询问土着居民，哪里有这种东西，居民们都不约而同地指向内地说：“古巴纳坎”。由于语言不通，哥伦布误认为是“××可汗”，进而联想成“中国的大汗”。因此，哥伦布确信自己到了中国的一个半岛。这真是一个了不起的发现！船员们也都为之鼓舞。哥伦布真是激动，他立即派了一个使团携带着西班牙国王的公函到内地去朝见中国皇帝。当然，他们不可能见到中国皇帝，也未找到城市、黄金和香料。印第安人给他们的仍旧是棉线团、鹦鹉和无足轻重的黄金饰品。如果说有什么稀奇的事，那就是这里有吸烟的习惯。这批欧洲人当时做梦都不会想到这种野草(烟草)后来竟会变得黄金般珍贵。
突如其来的兴奋很快又冷却下来，哥伦布再次搞错了。其实这里是加勒比海的古巴岛，在这里怎能见到中国的皇帝呢！可是，在哥伦布看来，没有找到黄金，是自己命运不佳，也许这里是中国最贫穷的地方。他仍然坚信这是中国的一个部分。
正当哥伦布纳闷的时候，他的部下告诉他说，已打听到离这里很远的东方，有个大岛，岛上居民脖子上挂着金项链，耳朵上垂着金耳环，胳膊上带着金手镯，甚至脚上也有金饰品。哥伦布听后，马上想起马可·波罗谈到在中国的东方，有个富庶的日本，出产黄金。他想，这次一定不会错，得赶快地去。
正在这时，“平特号”不见了。哥伦布想，一定是先到日本去寻找黄金了。的确是这样。他没时间计较这件事，率领两只舰火速赶往“日本”。12月6日，他们来到了一个风景优美、人口众多的大岛，当地人称“海地岛”。哥伦布利用两个星期勘探了北部海岸的大约1/3，绘制了相当准确的地图。这里土地肥沃，气候温和，水源充足。
12月20日，舰队来到了海地岛蕴含黄金最丰富的地方，这使哥伦布更加坚信这就是“日本”。岛民们友好地送给欧洲人许多金块，一位酋长赠给哥伦布一个金耳朵、金鼻子和金舌头的假面具。然而，这些西班牙人无视岛民们的这种友谊，竟贪得无厌地想要得到黄金，采取了极其卑鄙的抢劫手段，把岛民们的一切财物都据为己有。
后来，哥伦布又从一位老人那里知道，在海地岛南面还有一个岛，到处是黄金。哥伦布猜想，那一定也属于日本，为什么不到那弄更多的黄金呢？
不幸的是，正当他命令启航时，旗舰“圣马利亚号”搁浅了，只剩下最小的“宁雅号”，继续航行已不可能。哥伦布决定返回西班牙。
“宁雅号”满载了，由于无法容纳两艘舰上的全体人员，哥伦布决定将自愿在海地岛找寻更多黄金的39个人留下来，为他们备足一年用的粮食、酒、肉等食品，以“圣马利亚号”船为堡垒，还安了两门旗舰上的大炮。这就是欧洲殖民者在美洲建立的最初基地——纳维达德。
荣归西班牙1493年1月4日，哥伦布带着大量的黄金饰物、当时欧洲还没有的奇异植物和鸟的羽毛、十名俘虏来的“印第安人”，与部分船员踏上了返回西班牙的航程。两天后，意外地与“平特号”相遇。哥伦布以大局为重，没有惩处肇事者，与平松舰长修好，一起归航。
哥伦布凭借自己的海洋知识及直观感觉，选择了一条冬季向东横渡大西洋的最好路线。
归途，也并非是令人愉快的。顺利全速的一个多月的航行很快为接踵而至的灾难代替了。不仅蛀虫侵蚀着船壳，而且遭到了暴风雨的袭击。两艘舰在风浪中，各奔东西，很快就互相看不见了。小小的“宁雅号”被狂风巨浪打得东歪西斜，一会被浪头高高举起，像悬在半空似的；一会又被狠狠地摔到浪谷中，高大的水墙迅猛地向船压过来，人们仿佛掉进了大海的深渊，无法逃脱覆灭的命运。突然，巨浪又扑过来，轰的一声，整个“宁雅号”没入水中，人们觉得没有活命的希望了，转瞬间，船却似水洗似的从水中钻了出来，再次被推向浪尖……，就这样，人们挣扎在死亡线上。大自然的狂暴，使经验丰富、精力充沛的哥伦布也感到了恐惧，感到末日在即了。为了不让这次探险事业的成就泯灭，哥伦布拿出一张羊皮纸，尽可能地写下他已经发现的一切，并向国王和女王报告“圣马利亚”号已经搁浅，控告“平特号”开小差，要求给予惩罚。然后用蜡纸封上，装进木桶，投入大海，好让过往船员拾起转交收信者或海流带到海岸(359年后的1852年被美国船长在直布罗陀海峡发现)。
四天四夜的风暴终于停息了，“宁雅号”幸存下来，总算没有葬身海底。但好景不长，不到一个月，这条多灾多难的舰又遭到了风暴的袭击。舰被吹到了离里斯本不远的葡萄牙海岸，再次侥幸地得救了。哥伦布忙派急使，向西班牙国王和女王报告他到达“印度群岛”的喜讯，并率舰向巴罗士港进发。