Cristòfor Colom va arribar a Portugal el 1476 després del misteriós incident marítim del cap de Sant Vicenç. Aquí és on realment comença la història coneguda del descobridor d’Amèrica, més enllà de les incògnites que ens amaga el seu passat i que ell va ocultar envoltant la seva figura de misteri. Igualment, aquest període tampoc està mancat d’incògnites per resoldre: Colom va relacionar-se estretament amb el rei Joan II de Portugal, va navegar per les costes africanes, va arribar a Islàndia, i alguns autors asseguren que va “predescobrir” Amèrica.

Instal·lat a Portugal, Colom va viure durant nou anys en aquest país i en aquest temps va navegar amb diferents armadors per multitud de països, fonamentalment genovesos. No coneixem amb certesa les causes que van impulsar el navegant a quedar-se en terres portugueses, però aquesta estança va resultar fonamental per a la seva formació i per a la forja de les idees que l’impulsarien a intentar la quimera del viatge cap a les Índies a través de l’Oceà Atlàntic.
Des de Lisboa, Colom va treballar al servei dels mercaders genovesos Ludovico Centurione i Paolo di Nero, que van contractar els seus serveis per a realitzar el transport pel Mediterrani del sucre de l’illa de Madeira. Així, Colom va poder navegar per les costes occidentals d’Àfrica en un moment en el qual els portuguesos estaven a punt de fer el salt cap a l’Índic en la seva recerca de la ruta de les espècies. Igualment, el 1482, participant en l’expedició de Diego Câo, va navegar pel Golf de Guinea i va arribar fins a la fortalesa de San Jorge da Mina, un dels principals punts del comerç d’or africà.
Durant aquests viatges, realitzats en plena efervescència de la navegació i les exploracions mediterrànies i atlàntiques, el navegant va conèixer a Bartolomeu Perestrello, capità i governador de l’illa portuguesa de Porto Santo. Com a conseqüència de la seva relació amb Bartolomeu, el 1481, Colom va casar-se amb Felipa Monis de Perestrello, la seva filla, quan el governador ja havia mort. Felipa era una dama portuguesa amb un llinatge nobiliari i les dades ens indiquen que va tractar-se d’un casament de conveniència. Poca cosa més sabem sobre la seva relació, exceptuant que el matrimoni va tenir un fill, Diego, nascut a Porto Santo.

El matrimoni va viure a cavall entre Porto Santo i Madeira, fet que va permetre a Colom l’accés a la documentació de Bartolomeu: mapes, relacions de navegants, cartes, relats i restes de canyes i fustes desconegudes a l’Europa medieval que havien recollides en les proximitats de Porto Santo i les Açores arribades gràcies als corrents marítims. Això explica que Colom abandonés Lisboa per traslladar-se a un lloc com Porto Santo, on hauria realitzat el “predescobriment” d’Amèrica i elaborat el seu projecte.
En aquest sentit, Hernando Colón va escriure que el seu pare li havia explicat com fins a les Açores havien arribat “dos hombres de rasgos muy distintos a los cristianos”, probablement indis americans que des de l’Amazones haurien navegat sense rumb per l’oceà fins arribar a terres portugueses. Això hauria succeït cap a 1482-83.
També hi ha alguns autors donen per fet que en aquells anys Colom va trobar-se amb un nàufrag castellà o portuguès, el qual és identificat com a Alonso Sánchez Silva segons el relat de l’inca Garcilaso, que hauria estat arrossegat pels corrents marítims fins a l’altre extrem de l’Atlàntic, “predescobrint” Amèrica, i que hauria explicat a Colom el seu secret abans de morir. Això hauria succeït cap a 1477-78. En el relat de Bartolomé de las Casas també consta aquest episodi:
[El navegant supervivent del naufragi a Porto Santo] en reconocimiento de la amistad vieja o de aquellas buenas y caritativas obras, viendo que se quería morir, descubrió a Cristóbal Colón todo lo que les había acontecido, y diole los rumbos y caminos que habían llevado y traído y el paraje donde esta isla [La Española] dejaba o había hallado, lo cual [Colom] todo traía por escrito.
Colón tenía la certidumbre de que había de descubrir tierras y gentes como si en ellas personalmente hubiera estado […]. Tan cierto iba de descubrir lo que descubrió y de hallar lo que halló como si dentro de una cámara con su propia llave lo tuviera.
Un altre dels tresors indispensables per al descobriment d’Amèrica i que Colom hauria adquirit en aquest període seria un mapa del geògraf i astrònom florentí Paolo del Pozzo Toscanelli. Sembla ser que Toscanelli hauria enviat al rei Enric V de Portugal, l’anomenat El Navegant, un informe que afirmava l’existència d’un camí cap a Catay (Xina) si es navegava cap a ponent. En aquest mateix camí es trobarien també la mítica illa Antilla i Cipango (Japó). Colom s’hauria fet amb aquest mapa ja fos mitjançant el propi Toscanelli o gràcies a que els mercaders florentins Bartolomeo Marchionni i Lorenzo Berardi van aconseguir fer-se amb una còpia del document a Lisboa.

La carta nàutica de Toscanelli, basada en les teories del geògraf alexandrí Ptolomeu va permetre Colom arribar fins al continent americà gràcies a alguns errors que s’incloïen: Toscanelli calculava que la circumferència de la línea equatorial tenia una longitud de 30.000 quilòmetres, una quarta part inferior a la real. Gràcies a aquesta errada de càlcul, Colom va poder topar-se amb Amèrica en comptes d’arribar a l’extrem oriental asiàtic com va pensar que havia fet fins a la seva mort.
Només un any després del seu casament, possiblement com a conseqüència de les complicacions del part del seu fill Diego, la dona de Colom, Felipa Monis de Perestrello, va morir. Poc després es produïa la conjura contra la monarquia portuguesa: el duc de Bragança, amb la complicitat del seu cunyat, el duc de Viseu, va intentar, sense èxit, derrocar al rei Joan II de Portugal. En conseqüència, els conjurats contra la monarquia van ser perseguits, i la família de Felipa, emparentada amb els Bragança, va ser va ser una de les represaliades. Alguns autors consideren que aquest seria el principal motiu pel qual Colom va veure’s obligat a traslladar-se a Castella.

D’altres autors, però, apunten que el fet que, el 1486, Colom abandonés Portugal va estar relacionat amb que Joan II desestimés el seu projecte de viatge a les Índies travessant l’Atlàntic. I és que cap a 1484 Colom ja havia ofert a Joan II el seu projecte descobridor. La proposta, però, va ser desestimada després que la Junta dos Matemáticos trobés que la teoria de Colom era un disbarat. Igualment, els desmesurats honoraris, tant econòmics com honorífics, que Colom exigia per a realitzar l’expedició també van influir en el rebuig del monarca. Segons Las Casas, Colom havia ofert a Joan II el mateix que posteriorment oferiria als Reis Catòlics, és a dir:
Que por la vía de Poniente, hacia el Austro o Mediodía descubriría grandes tierras, islas y Tierrafirme, felicísimas, riquísimas de oro y plata, y perlas y piedras preciosas y gentes infinitas; y que por aquel camino entendía topar con tierras de la India, y con la gran isla de Cipango y los reinos del Gran Khan.
Tanmateix, segons el testimoni d’Hernando Colón, alguns dubtes devia crear la hipòtesi de Colom en la monarquia portuguesa perquè Joan II va fer enviar una caravel·la a Cabo Verde per a comprovar si la hipòtesi colombina podia ser certa. Aquesta primera comprovació va fracassar, però es produirien nous intents a través d’expedicions que marxaven cap al ponent sense obtenir cap tipus de resultats. En aquest sentit, Las Casas afirma que Colom va marxar de Portugal “lo más secreto que pudo, temiendo que el rey lo mandara detener” ja que Joan II l’havia fet buscar per comprovar la ruta indicada després del fracàs de les expedicions. Colom es trobava desacreditat i no tenia més remei que fugir.
Ja fos com a conseqüència de la conjura del duc de Bragança o per la negativa de Joan II a finançar la seva expedició cap a les Índies, o per algun altre motiu relacionat potser amb el seu passat enigmàtic, la qüestió és que Colom va abandonar Portugal amb el seu fill Diego per passar a Castella i oferir el seu projecte als Reis Catòlics. La quimera del viatge cap a les Índies estava cada cop més a prop.