也许是一四八三年，他向葡萄牙王约翰二世提出建议，结果被拒绝，次年他前往西班牙。两年之后，他到了西班牙宫庭所在地科尔多瓦。他向伊莎贝拉提出同样的建议，结果又被拒绝。一四八八年，他回到里斯本，遇到他的兄弟巴尔索罗缪，他刚从发现好望角探险航海中归来。为这个长达一万三千英里的航行所鼓励，又请他的兄弟到英法两国去向亨利七世和查理八世提出这个计划。
结果还是到处碰钉子，一四八九年他又回到西班牙。最后在一四九一年，他说服了美狄亚公爵相信他的计划是可行的。最后，女王伊莎贝拉说等格拉纳达被攻占之后愿意考虑这个计划。从这一点看来，她对这个计划已有几分相信，因为哥伦布提出的要求实在是夸张到了极点。他要求指派自己为大西洋海军上将，一切新发现领土的总督，而且对获得的一切财富都要按总值抽取八分之一。现在他心里最重视的还是十字军的思想--这也是遗传作用--格拉纳达陷落后不久，哥伦布上书斐迪南和伊莎贝拉，要求他们派他去印度，设法使大可汗的人民和国家皈依天主教。由于新获胜利增强了伊莎贝拉的信心，哥伦布的条件被接受了。
一四九二年四月十七日，他与西班牙政府签订了一个条约。西班牙国王和女王也用拉丁文(当时的国际通用文字)写了一封国书，要他转致大可汗。
一四九二年八月三日星期五上午，哥伦布率领三艘小船从帕罗斯扬帆出海：“圣玛利亚号”重一百吨，“平塔号”重五十吨，“尼娜号”重四十吨。全部水手总数为九十人，此外还有三十个人，包括著名航海家阿隆佐兄弟和精通七国语言的犹太人托里斯作为译员。八月九日到达加纳利群岛，在那里停留到九月九日才再度前进，这次是进入了未知的海域。十月十二日星期五上午二时看见陆地，在拂晓时正式登陆，可能是在瓦特林岛。哥伦布称之为圣萨尔瓦多，对来欢迎他们的土人，他很有意义的称之为“印地安人”。
他继续航行，于十月二十八日抵达古巴，他认为这应是中国大陆的一部分，也就是说已到大可汗的领域了。于是他派两个从者去寻找该国宫庭，并呈递伊莎贝拉和斐迪南的国书。接着他向东航行又到了海地，他以为这就是日本，定名为希斯潘洛拉，一四九三年一月四日他开始返回西班牙，于三月十五日到达帕罗斯。他被召往巴塞罗那宫中，得到了凯旋的荣遇。毫无疑问，大家都认为他的理论是正确的：古巴就是中国东岸，海地就是日本北端。所以已经找到了一条通往亚洲的海上捷径，比葡萄牙人想发现的更短。据马可波罗记载，这些地方充满了财富，所以这对夫妇国王简直喜极而泣，认为这些无限的财富是上帝的恩赐，作为他们在格拉纳达击败摩尔人的酬劳。
到底哥伦布是英雄还是骗子，这并无太大关系，事实总在那里，这个发现是人类历史上空前绝后的大事。现有的地中海世界就此崩溃，千年来的壁垒被摧毁。伊斯兰教徒不再能在地中海的两端出口处封锁这个世界。眼界放宽之后，人类的活动和思想也就开辟了新途径。地中海在许多世纪一直都是欧洲人的樊笼，现在已经锁不住了。人类发现自己自由了，同时也增强了力量。当他们对新大陆扩展领土时，人类的权力也随之增长。简而言之，一种“新人类”已经诞生了。
