当完成补给后，10月13日，船队离开费罗岛，向“西偏南”方向驶去。因为他认为沿此方向航行，定能在中途发现陆地，但海军上将没能发现陆地，却缩短了至少一个星期的航程。这次航行历时21天，航行820里格，折合2608海里，非常接近海员梦寐以求的完美航行。因为船队只是在10月26日前夕受到一次强烈的雷暴风的袭击，被撕裂了一些船帆，摧折了少量的桅杆，但仅过4小时后，风暴就过去了，船队损失比较轻微。11月3日早晨5点左右，黎明将至的时刻，“玛丽亚加朗特”号上的一位年老的舵手在左舷船头发现了陆地。这一天正是主的安息日，海军上将把这片陆地命名为多米尼加，土著人称它为凯雷。在右舷出现的陆地称为圣玛丽亚拉加朗特岛。天亮以后，船队陆续发现了瓜德罗普岛、德西拉德岛和拉桑特群岛等。令人惊疑不已的是，德西拉德岛两边的任何一条航道都是以后历史上船队通行的咽喉要道，因为，任何错离此岛的附近航线都因信风和暗礁的影响可能使航船倾覆，这不能不说是海军上将的极大幸运，而海军上将在这次西航中发现了这样一条从欧洲到西印度群岛最远和最短的航线，更是航行探险史上的一个奇迹。
女王命令返航的消息传到哥伦布这里，他既感到非常吃惊，又非常委屈。于是，他决定立刻回两班牙，向国王和女王陈述实情。
1496年，归国的船队出发了。随行的人除了老弱病残船员外，还有30多个土人，高拉波酋长也在内。哥伦布没把他当俘虏看待，而是一心想用基督教义感化他。回航时，由于强烈暴风雨的阻隔，行程受误，当粮食不够，乃至后来断绝时，哥伦布坚决拒绝了有的船员杀死土人当粮食或把他们扔下海里的建议。
第三次远航
经过3个多月的航行，他们终于回到西班牙。但再也没有了上次那样的热烈欢迎的场面，而且哥伦布晋见国王时，国王也对他表现出极冷淡的态度，不少大臣还在背后讥笑他，只有女王还对他仍然很客气。哥伦布虽然非常伤心，但不久，他又再次鼓起勇气进宫晋见女王，请求准许他第三次远航。女王被他的真诚和热心所感动，终于答应设法为他筹款。
又经过不知多少波折，哥伦布第三次远航探险所需的船只、物资和费用，终于筹办齐全了。这一次远航的规模比前两次都大，船队由8艘大型帆船和40艘小型帆船所组成。
1498年5月30日，第三次远航开始了。这次船队从圣卢卡港出发，他们的目标首先是阔别两年多的希斯盘纽拉岛。
航行的最初几天，虽然海上风平浪静，但天气却非常炎热，船上携带的许多食物都已变坏，食用淡水也逐渐减少，水手们的情绪也因此变得非常暴躁。好不容易克服了天热的考验，航行了两个月以后，他们才抵达了一个大岛的东南岸。岛上的景色和其他的岛屿一样，到处长满了茂密的树林，郁郁苍苍，直插云天，令第一次前来的人赞叹不已。哥伦布的船队沿着海岸慢慢航行，大家都陶醉在美丽壮观的景色之中，却绝对没有想到这座岛的对岸就是南美洲大陆。哥伦布再一次失去了直接发现美洲大陆的机会。
6月7日，船队到达马德拉群岛。多年前克里斯朵夫曾在这里生活过，并且经商赚了钱。老朋友们给他举行了一个像样的欢迎会。2次航行结束后两年来一直处于失落和孤单中的哥伦布第一次满足了虚荣心。而他则率队击溃了几艘法国海盗船作为报答。
离开马德拉群岛后，分出3条船给伊斯帕尼奥拉岛送给养，克里斯朵夫领另3条船向南驶去。这次克里斯朵夫决定到赤道附近去，根据一位地理学家兼珠宝商的建议，赤道上某些热带国家有黑皮肤和棕皮肤的人，他们有数不尽的珠宝、黄金和香料。
从佛得角向南，驶去了大约100公里，船队正处于信风区中间的赤道无风区。这是一个奇热无比的地带，热得好像船只和人要一起被烤焦了，木桶干裂，腌肉腐烂，粮食变得像火一样灼人口舌。大家都陷入了半昏迷状态，找不到一个人能有力气到甲板下去取点水。酷热持续了8天，然后是雷阵雨。但是受尽煎熬的船员们却没有体力去收集宝贵的雨水。没被烤焦的神智还在运动，大家惊恐万状，因为中世纪的宇宙学家们断言，太阳在遥远的南方能烤死一切生物，这里肯定就是那个地方。7月31日，克里斯朵夫知道再也熬不下去了，只好下令转向西方。
中午，他们发现了陆地，在这个岛上取水时，看见了远方长满浓密森林的海岸，那里就是南美洲大陆。统帅命名为特立尼达岛。大家高兴极了，欢乐地吟诵和歌唱起《万福啊，慈爱的圣母》，以赞美上帝和圣母玛丽亚的恩赐。在欢歌声中，船队胜利走完了第三次向西航行的全部路程。
8月13日，船队通过北部的狭窄海峡驶离帕里亚湾，这里浪高流急，哥伦布称它为龙口。连续两天，船队一直沿帕里尼半岛北边航行。这里的海岸线一直延绵好像没有尽头，哥伦布此时又修整了他的看法。猜测这里可能是“一个很大的大陆的一部分”。但是他的头脑中充满了荒诞的地理概念，疾病妨碍他作出正确的判断。他中止了这一次极其重要的探险。他认为此时回到伊斯帕尼奥拉对他来说是头等大事。在船队即将到达一个他叫做玛嘉丽塔的岛屿时，他命令转向朝北行驶。他没有察觉这里是一块盛产珍珠的宝地，如果他能派人在此开采的话，所获珍珠的价值将超过伊斯帕尼奥拉所产黄金的数百倍。
在哥伦布长期不在伊斯帕尼奥拉的情况下，他的弟弟巴托罗缪下令，在岛的东南岸边奥扎马河口上建立新的首府，叫做圣多明各。这里比伊莎贝拉条件优越得多，土壤肥沃，卫生状况良好，有固定的淡水供使用，还是一个可避风暴的良港。时至今日，圣多明各仍然是加勒比地区最古老的城市，是多米尼加共和国的首都。
8月31日，哥伦布一行到达新的首府。由于缺少劳力，城市建设只进行了一半。更为重要的原因是巴托罗缪·哥伦布必须把精力集中在别的事情上。作为代理总督，他未能赢得人心。对他的不满情绪逐渐增长，后来终于爆发了由岛上大法官弗朗西斯科·罗尔丹领导的叛乱。哥伦布到达时，罗尔丹和他的追随者正在岛屿的西南边省份哈腊瓜和当地的酋长贝西奇奥拉关系，其中还有贝西奇奥的妹妹——漂亮的安娜考纳。她是死在去西班牙的船上的酋长卡奥纳波的遗孀。
哥伦布从加纳利派出的三艘快帆船由于计算的错误未能直达圣多明各，错开的距离竟达好几百里。更为糟糕的是他们到达的地方竟是罗尔丹现在所在处。船长们不知道罗尔丹发动的叛乱，欢迎他登船，交给他给养和武器，还让自己的船员上了岸。这些人中间许多都是罪犯，罗尔丹轻而易举地把这些人收编，结果是他率领的这伙约70多叛乱分子组成的队伍大大地增强了威慑力量。
罗尔丹在哈腊瓜扎下营寨，在那里形成了一个由他发号施令的独立王国。为了壮大自己的声势，罗尔丹公开宣布全面“保护”印第安人的政策，以此来和伊莎贝拉城的巴托罗缪分庭抗礼。他所谓的“保护”实际上是把印第安人分给西班牙殖民者个人所有，成为附属于他们的私有财产。哥伦布从西班牙弄来的是劳动者，而他们在得到印第安人以后个个都当了主人，过着强迫印第安人劳动并让他们服侍自己的王公贵族般的生活。罗尔丹的这一项政策既缓和了与印第安人的全面冲突，又赢得了大多数西班牙殖民者的拥护。
这时，在西班牙国内，不断地有人在国王面前诽谤哥伦布。由于哥伦布从第三次远航以后，一直没有什么收获献给朝廷，没再讨得国王的欢心，宫廷里的大臣就乘机利用一切机会诬告他。说他和弟弟们已经独占新陆地，另立新王国啦，说他要把新陆地卖给外国啦，各种谗言不断涌到国王的耳边。听得多了，国王也就开始对哥伦布起了疑心。于是，国王便派遣全权大臣法兰西斯驾船西行，负责了解情况。
法兰西斯是个有名的残暴刚愎的人，而且他一直反对哥伦布。如今他成了国王的钦差大臣，大权在握，一些正直而同情哥伦布的大臣私下里议论此事，都不禁替哥伦布捏着一把冷汗，为他的命运担心。
哥伦布虽然深知自己并没有什么罪过，但是，法兰西斯既然是受国王之命前来逮捕他，那么他就不愿违背这命令。于是他一动不动地静静地站在门口，两眼坦然自若地看着法兰西斯。他心想：国王肯定是被小人的谗言所惑，才下令派人来抓我。自己既然身为国家海军总提督，服从国王的命令就是遵守国法。无论是什么，都不该违抗。只要回国见到了国王，问明白原因，再向国王表明自己的心迹，那么，今天受到再大的耻辱，也就不算什么了。
想到这里，哥伦布毫不犹豫地伸出双手，自动等着士兵来把自己铐住。