Ngày 10 tháng 3-1496, Colombo khởi hành đi Tây Ban Nha. Tại đó ông phải tự bảo vệ mình chống lại những lời tố cáo của Cha Boil, Margarite và rất nhiều người khác bị vỡ mộng, hoặc bị ốm, đã bỏ những đảo giữa Bắc và Nam Mỹ để trở về quê hương họ.
Khi lên đường trở về Tây Ban Nha, Colombo đã giao nhiệm vụ cho Bartolomeo xây dựng một thủ đô mới. Bartolomeo đi đến bờ biển phía Nam và chọn một hải cảng thiên nhiên rất tốt tại một cửa sông, đất đai đặc biệt phì nhiêu với nhiều dòng nước chảy qua, và cát thì chứa nhiều vàng. Ông đặt tên cho vùng định cư mới này là Santo Domingo để tưởng nhớ cha của họ là Domenico. Ngược lại Colombo luôn luôn dùng những tên để tỏ lòng tôn kính Thiên Chúa giáo hay nước Tây Ban Nha. Ông ta chỉ phá vỡ thói quen ấy một lần, khi ông đặt tên Savona, và như ông đã nói rõ, là để tưởng nhớ Michele da Cuneo là bạn ông ở Savona, chứ không phải vì bản thân ông hay gia đình ông. Phải quên đi nguồn gốc ngoại quốc của ông và sự tôn trọng của ông đối với xứ sở mà ông đã nhận làm sinh quán là tuyệt vời. Bartolomeo không có những đắn đo như thế và chỉ muốn tưởng nhớ người cha mình khi đặt tên thủ đô mới. Một đôi khi Colombo gọi thủ đô ấy là Isabela Nueva. Trong khi dân chúng ở Isabela cũ liên tục sụt giảm cho đến khi thành phố bị bỏ hoàn toàn. Thành phố mới nhanh chóng nẩy nở và phát triển; đó là một thủ đô thực sự. Philip II gọi đó là "cái thang, là hải cảng, là chìa khóa đến tất cả các đảo giữa Bắc và Nam Mỹ".
Cuộc vượt biển trở về Tây Ban Nha rất dài ngày, kết thúc ngày 11 tháng 6 tại Vịnh Cádice. Cùng đi với Colombo là 125 người Công giáo và một số ít người sống sót trong số 30 người Anh- diêng đã lên tàu tại La Isabela. Khó hiểu tại sao hai chiếc tàu nhỏ mà theo thường lệ chỉ chở khoảng hai mươi bốn thủy thủ, đã có thể chở nhiều người như thế, những điều đó cho thấy nhiều người Tây Ban Nha rất muốn rời khỏi quần đảo Antilles. Những người đã di cư đi tìm thiên đường theo sự miêu tả của Colombo nay trở về mặt mũi và thân hình gầy mòn hốc hác do chịu khổ cực lâu ngày.
Lần này Bernaldez trông thấy viên Đô đốc của Đại Dương, Phó vương và Tổng trấn của những đảo giữa Bắc và Nam Mỹ, "mặc quần áo màu của những tín đồ Francescani ngoan đạo, với quần áo vải bao bì và dây thừng của thánh Francesco để thực hiện một lời nguyền". Quả thật Colombo có mang một dây thừng để thực hiện một lời thề, nhưng mặc quần áo của một thủy thủ bình thường may bằng vài thô dễ lẫn với quần áo của tín đồ Francescano. Tuy nhiên đó là quần áo khiêm tốn của một thủy thủ, không thích hợp với một thuyền trưởng hay Đô đốc. Hy vọng gây ấn tượng khi ông đến thăm Vua và Hoàng hậu, ông đã đeo lên cổ con trai Caonabó một dây xích vàng nặng sáu trăm castellanos. -
Cuộc đến thăm Vua và Hoàng hậu cũng rất khác cuộc đến thăm sau chuyến đi thứ nhất. Colombo báo tin cho Vua và Hoàng hậu biết việc ông đã về, ngay khi ông xuống tàu ở Cadice và ông đi Seviglia để đợi lệnh gọi của Vua và Hoàng hậu. Đó là một thời gian chờ đợi lâu dài. Boil và Margarite đã có âm mưu tại triều đình trong nhiều tháng và bây giờ Aguado cũng tham gia với họ bằng một tập hồ sơ tố cáo và tường trình. Về vấn đề quan hệ giữa Colombo với Vua và Hoàng hậu Công giáo, một số nhà sử học cố đối lập thái độ của vua Ferdinando với thái độ của Hoàng hậu Isabella, mô tả nhà vua thành người nghi ngờ, không bao dung, và thù địch còn Hoàng hậu thì nhạy cảm, có cảm tình và khâm phục. Lập trường đó không có chứng cớ đáng tin cậy.
Tuy nhiên có một giả thuyết có thể tin cậy được cho rằng Colombo có nhiều kẻ thù trong đám người Catalani hơn là trong những người Castigliani. Thậm chí một số người còn nói về bè lũ Catalani tại triều đình, không những vì những người hữu quan mà còn vì sự nghiệp của cuộc phát kiến vĩ đại trở nên một thành tựu riêng biệt của nhóm người Castigliani: "Thông qua Castila và Leon, Colombo đã phát hiện ra một thế giới mới". Nhưng nếu Margarite và Cha Boil là người Catalani Aguado rất đối địch lại là người Castigliani gốc Siviglia, cũng như người thợ vàng Zedo. Zedo bị trừng phạt và đưa về nước vì đã phao tin rằng những cục vàng và những đồ châu báu Hispaniola là hợp kim thường. Lời tố cáo đó dễ dàng chứng minh là một lời nói dối, nhưng lời vu cáo bay đi xa, không những lời vu cáo của Zedo mà cả của những người khác cũng lan truyền. Lúc này Colombo đã mất sự ủng hộ của dư luận công chúng. Vua và Hoàng hậu vẫn tỏ lòng kính trọng và biết ơn ông, điều đó thể hiện rằng trong bức thư viết từ Almazan ngày 12 tháng 7 năm 1496. Bức thư ấy lịch thiệp và nhân từ, tuy nhiên nó hoãn cuộc tiếp kiến. Tháng 8 Colombo nhận được một bức thư khác đặc biệt quan trọng. Trong thư Isabella hỏi ý kiến ông về con đường tốt nhất cho những tàu biển rời vịnh Biscaglia với Công chúa Juana và những người hầu cận của công chúa, đưa công chúa đến Flanders để kết hôn với Hoàng tử nước Áo Philip. Hoàng hậu vẫn còn kính trọng tài năng về đi biển của Colombo. Colombo đã gợi ý ngay tức khắc và phúc đáp của Isabella ngày 18 tháng 8 lời lẽ nhã nhận đầy lòng biết ơn.
Mùa thu Vua và Hoàng hậu ở Burgos, tại dây họ tổ chức một đám cưới khác, đám cưới của hoàng tử Don Juan với Công chúa Margaret, con gái Hoàng đế Maximilian. Cuối cùng tại đó Colombo đã được yết kiến Vua và Hoàng hậu. Vua và Hoàng hậu bày tỏ thiện chí và trìu mến đối với ông, bác bỏ những lời tố cáo và vu khống của Cha Boil, Margarite và Aguado. Những lời phê phán đó, một số không phải là không có cơ sở, đã không phá được lòng biết ơn và sự tin cậy của Vua và Hoàng hậu. Kẻ thù và những người bôi xấu Colotnbo chỉ đạt được một điều là nhà vua chưa thừa nhận tước adelantado của Bartolomeo. Ban thưởng tước đó không phải là quyền của Colombo mà là quyền của Vua và Hoàng hậu. Năm sau, ngày 22 tháng 7 năm 1497 Vua và Hoàng Hậu mới ban tước đó, làm ngơ trước thực tế là Colombo đã ban tước đó trước rồi.
Tại cuộc tiếp kiến thứ nhất ở Burgos, Colombo đã yêu cầu tàu và đồ tiếp tế cho cuộc du hành thứ ba. Ông ta theo đuổi ý tưởng cố định của mình, mục tiêu mà ông chưa đạt tới: Ấn Độ. Colombo phải tới Ấn Độ. Người ta bắt đầu nói về chuyến đi thứ ba vào mùa thu 1496, nhưng Colombo gặp phải những khó khăn và những vấn đề nghiêm trọng hơn nhiều so với việc chuẩn bị cho chuyến đi thứ hai. Cuối cùng sự bền bỉ của ông đã vượt mọi trở ngại, và ngày 13 tháng 5- 1498 ông đã khởi hành chuyến đi phát kiến thứ ba.