Vào thời trẻ của Colômbô, Genoa là một trung tâm đóng tàu và hàng hải phồn thịnh với những nhà trắc địa chiếm lĩnh thị trường họa đồ đường biển ở phía tây Địa Trung Hải. Họ cũng đã vẽ những bản đồ các phần của bờ biển châu Phi vừa mới được người Bồ Đào Nha khám phá.
Genoa, "thành phố xinh đẹp và hùng mạnh trên bờ biển", là nơi Colômbô đã trải qua 22 năm đầu đời, từ lâu đã luôn luôn tranh giành quyền bá chủ đường biển ở phía đông Địa Trung Hải với Venice. Từ một nhà tù ở Genoa, nhà thám hiểm Marco Polo người Venice đã đọc cho người ta viết lại những cuộc hành trình của ông. Vào thời trẻ của Colômbô, Genoa là một trung tâm đóng tàu và hàng hải phồn thịnh với những nhà trắc địa chiếm lĩnh thị trường các họa đồ đường biển ở phía tây Địa Trung Hải. Họ cũng đã vẽ những bản đồ các phần của bờ biển châu Phi vừa mới được người Bồ Đào Nha khám phá. Rất có thể Colômbô đã bắt đầu học nghệ thuật vẽ bản đồ tại Genoa, rồi đem áp dụng ở Lisbon cùng với em của ông. Hiển nhiên Genoa luôn luôn là quê hương và cái nôi của những nhà thám hiểm như Colômbô (1451-1506) và John Cabot (1450-1498), nhưng những công trình thám hiểm đường biển lớn đòi hỏi nhiều nguồn lực to lớn hơn, một hậu cứ rộng hơn và một hướng đi xa hơn về phương tây vào thời kỳ mà người Hồi nắm giữ phần lớn đất phía đông Địa Trung Hải.
Năm 1476, khi Colômbô đang phục vụ trên một tàu lớn trong một toán lính hộ tống một chuyến hàng qua eo Gibraltar và đi lên phía bắc châu Âu, tàu của ông bị một hạm đội của Pháp tấn công và đánh chìm. May thay sự kiện này xảy ra gần Lagos, chỉ cách xa bờ biển Bồ Đào Nha một ít dặm, là nơi hoàng tử Henry đặt căn cứ của mình. Colômbô lúc đó là một thanh niên hai mươi lăm tuổi đã dùng những mái chèo dài kết thành phao và đã vào được bờ thoát nạn.
Hóa ra đây lại là nơi dừng chân may mắn và tuyệt vời do trời định cho chàng trai đi biển đầy tham vọng này. Những người ở Lagos hết sức thân thiện đã cho Colômbô thay quần áo và ăn uống, rồi đưa anh tới Lisbon gặp em trai mình là Bartolomeo.
Khi Colômbô cùng em trai mình mở một cửa tiệm ở Lisbon, những con tàu của Bồ Đào Nha vẫn đang lần mò dọc xuống bờ biển phía tây châu Phi và mới chỉ đến được Vịnh Guinea. Nhưng toàn thể châu Phi theo như Ptolêmê đã hình dung ra vẫn chưa được các nhà hàng hải thám hiểm hết. Cuối năm 1484, khi Colômbô trình lên vua Joan II của Bồ Đào Nha "Công trình thám hiểm Indies", có vẻ như con đường biển phía tây không những có thể ngắn hơn nhưng có lẽ là con đường duy nhất để đến Indies.
Trước đó cả một thập niên, vị vua tiền nhiệm của vua Joan là Alfonso V đã từng nghĩ tới khả năng có một con đường biển phía tây dẫn tới Indies. Ông đã tham khảo ý kiến của một số chuyên gia người Florentin là Paolo dal Pozzo Toscanelli (1397-1482), vừa là bác sĩ, nhà thiên văn và nhà trắc địa. Ông này đã viết một lá thư vào ngày 25 tháng 6, 1474, gợi ý "có một con đường biển dẫn tới đất Gia Vị, ngắn hơn con đường đi qua Guinea". Và Toscanelli đã tin tưởng thuyết phục vua cho thử con đường phía tây này. Trong thực tế, chính Toscanelli đã vẽ ra một bản đồ hàng hải của Đại Tây Dương và ông đã gởi bản đồ này kèm theo lá thư tới Lisbon.
Cuối năm 1481 hay đầu năm 1482, khi Colômbô nghe biết về lá thư này, ông đã phấn khởi viết thư cho Toscanelli và xin thêm thông tin. Toscanelli hồi âm bằng một lá thư khích lệ kèm theo một bản đồ khác. Colômbô đã mang theo bản đồ này trong hành trình của mình để chứng minh Toscanelli đã nói đúng.
Sau khi đã cảm thấy chắc chắn, Colômbô giờ đây cảm thấy say mê muốn thử thời vận to lớn này. Chuyện khó là phải làm sao thuyết phục các nhà tài trợ. Để thuyết phục những nhà đầu tư bỏ vốn vào một dự án mới mẻ như thế, Colômbô phải nghiên cứu kỹ lưỡng những tài liệu của các người đi biển, các nhà trắc địa, các nhà thần học và triết học.
Năm 1484, Colômbô chính thức đệ trình Công Trình Thám Hiểm Indies lên vua Joan II. Lúc đầu vua Joan rất phấn khởi về kế hoạch của chàng trai năng nổ người Genoa này. Nhưng khi Colômbô xin vua cấp cho nhân viên và trang bị ba chiếc tàu caravel, nhà vua "đã không mấy tin tưởng" và cho rằng Colômbô chỉ là "một tay khoác lác và đầy tưởng tượng viển vông".
Tuy nhiên vua cũng thấy khá thuyết phục vì tài ăn nói của Colômbô và đã giao kế hoạch này cho một tổ chuyên gia xem xét. Tổ chuyên gia này đã bác bỏ kế hoạch. Họ bác bỏ kế hoạch này không phải dựa trên bất đồng quan điểm của họ về hình cầu của trái đất, vì thời đó, những học giả châu Âu không còn nghi ngờ gì điều này. Nhưng tiểu ban này có vẻ thắc mắc vì Colômbô đã tính toán quá thấp đường dài trên biển dẫn tới châu Á. Và trong thực tế, những thắc mắc của họ chứng tỏ có cơ sở hơn những hy vọng của Colômbô.
Tiểu ban chuyên môn của vua Joan II không để mình bị thuyết phục bởi những hi vọng của Colômbô. Trong thực tế, họ có lý hơn những hi vọng hão huyền của chàng trai Colômbô năng nổ. Đường chim bay từ Canaries tới Nhật Bản là mười ngàn sáu trăm hải lý và những ước tính của họ có lẽ gần đúng với con số này. Vì thế họ không cổ vũ vua đầu tư vào một kế hoạch quá mơ hồ trên lý thuyết của Colômbô.
Năm 1485 là một năm xui xẻo cho Colômbô về nhiều phương diện. Năm đó vợ ông chết và ông cùng con trai 5 tuổi là Diego rời đất nước mà ông đã sinh sống phần lớn tuổi trưởng thành của mình. Ông sang Tây Ban Nha với hi vọng gặp nhiều may mắn hơn cho dự án luôn ám ảnh ông.
Tại đây ông đã thành công lớn cả về buôn bán lẫn ngành hàng hải. Được em ông là Bartôlômêo trợ giúp, trong bảy năm tiếp theo, ông đi đến các triều định của Tây Âu để trình bày Công Trình Thám Hiểm Indies của mình. Tại Tây Ban Nha, lúc đầu ông đã gợi được sự quan tâm của Bá tước Medina Celi, một chủ tàu giàu có ở Cadiz. Lẽ ra Celi đã có thể tài trợ cho ông ba chiếc tàu caravel nếu hoàng hậu của Tây Ban Nha không từ chối. Nếu thực hiện được, kế hoạch thám hiểm này chắc chắn phải là một kế hoạch hoàng gia. Phải một năm sau hoàng hậu mới cho Colômbô triều kiến. Và rồi, bà cũng đã cho một tiểu ban nghiên cứu, đứng đầu là Hernando de Talavera, cha giải tội của bà, để nghe Colômbô trình bày chi tiết những đề nghị của mình và cho lời nhận xét.
Lúc này Colômbô phải trải qua những năm đen tối vì thái độ thư lại của hoàng hậu Isabella và các cận thần của bà. Tiểu ban đã cho những kết luận đánh giá lý thuyết của họ, nhưng không chấp nhận cũng không bác bỏ kế hoạch. Các chuyên gia trong tiểu ban tiếp tục mổ xẻ kế hoạch và bắt Colômbô phải chờ đợi với một món lương ít ỏi của triều đình.
Trong thời gian chờ đợi cuộc thương lượng kéo dài này, ông sực nhớ vua Joan II đã tỏ ra rất thân thiện với ông vào những năm 1484-85, thế là ông quyết định quay trở lại Lisbon để thử một lần nữa. Từ Seville, Colômbô viết một lá thư gửi vua Bồ Đào Nha, trình bày những hi vọng của mình. Nhưng lần trước, khi rời Bồ Đào Nha, Colômbô đã ở trong một tình trạng tài chánh khốn quẫn và còn nhiều món nợ chưa thanh toán. Vì thế ông không dám quay trở lại Lisbon trước khi được vua bảo đảm không bị bắt vì nợ nần. Vua đồng ý, khen ngợi tài năng của Colômbô và truyền cho ông cứ đến. Vua cảm thấy phấn khởi trở lại và chắc chắn là vì hai chuyến hành trình của Dulmo và Estreito tới Antilla đã thất bại. Ngoài ra, vua cũng không được tin gì về cuộc hành trình 7 tháng trước của Brrtolomeo Dias", người đã đi tìm con đường biển phía đông tới Ấn Độ trong chuyến thám hiểm thứ hai mươi của Bồ Đào Nha.
Rốt cuộc Colômbô đã chọn phải thời điểm tồi tệ nhất. Đúng lúc Colômbô và em mình là Bartolomeo đến đó vào năm 1488, thì Bartolomeo Dias cũng đã thành công trở về, mang theo tin tốt lành là họ đã đi vòng qua Mũi Ảo Vọng và đã phát hiện ra quả thực có một đường biển phía đông tới Ấn Độ. Thành công và triển vọng của Dias đã làm cho vua không còn hú tới Colômbô nữa. Nếu đã có con đường dễ dàng ở phía đông, thì còn cần gì nghĩ tới một con đường theo hướng khác?
Hai anh em Colômbô lúc này chỉ còn hi vọng mong manh là sự thành công của Bồ Đào Nha về phía đông có thể khích động sự cạnh tranh của các nước khác về các kế hoạch theo một hướng khác. Có vẻ như Btolomeo đã đến nước Anh nhưng không thuyết phục được vua Henry VII. Ông đi sang Pháp, cố gắng thuyết phục vua Charles VIII. Lúc đầu vua không quan tâm, nhưng bà chị của vua đã giúp đỡ cho Bartolomeo ở lại Pháp và làm công việc vẽ bản đồ.
Trong lúc đó Colômbô ở Lisbon quay trở lại Seville và ông thấy vua Ferdinand và hoàng hậu Isabella vẫn còn đang do dự. Thất vọng, ông lên tàu đi Pháp để giúp Bartôlômêo thuyết phục vua Charles VIII. Bất ngờ, khi ông đang trên đường đi, hoàng hậu Isabella đột ngột quyết định giữ Colômbô ở lại Tây Ban Nha. Có thể hoàng hậu hiểu rằng Colômbô đang định đi đề nghị hợp đồng của ông cho nước láng giềng. Bà đã quyết tâm đánh đổi bất cứ điều gì để tài trợ cho kế hoạch của Colômbô.
Trong quyết định vào phút chót của mình, hoàng hậu đã phái sứ giả tới gặp Colômbô trước khi ông cập bến nước Pháp. Cuối cùng, tháng 4, 1492, tám năm sau khi Colômbô đề nghị kế hoạch của mình lần đầu tiên với vua Bồ Đào Nha, ông đã ký kết những hợp đồng với triều đình Tây Ban Nha, kết thúc những năm đi thuyết phục và thương lượng. Giờ đây, tiêu điểm duy nhất của Colômbô là biển.