1476年5月にはチェントリオーネ家やスピノラ家、ディ・ネグロ家などジェノヴァ商人団に雇われ、乳香をイギリスやフランドルへ運ぶ商船隊に参加し、ベカッラ号に乗り込んだ。しかし8月13日[5]、この船団がブルゴーニュの旗を掲げていたため、ポルトガルのサン・ヴィセンテ岬沖で当時敵対していたフランス艦船から攻撃を受け、船は沈没した。コロンブスは櫂につかまって泳ぎ、ポルトガルのラゴス(en)までたどり着いた。なお、コロンブスが乗船していたのはフランスとカタルーニャ連合の船であり、いわばジェノヴァ船団を攻撃した側にいたという主張もある[注 8]。 彼はジェノヴァ人共同体の助けを借りてリスボンへ移った[3]。この時期は1477年春以降と考えられる[6]。そこには、地図製作に従事する弟のバルトロメが住んでおり、コロンブスは弟と一緒に地図作成や売買をしながら、たびたび航海にも加わっていた。1477年2月には、イギリスのブリストルを経てアイルランドのゴールウェイ、そしてアイスランドまで向かった。アイスランドには、かつてヴァイキングが北アメリカに植民地を築いたという「ヴィンランド伝説」があったが、コロンブスがこの伝承を耳にしたかどうかは分かっていない[7]。 1479年末、コロンブスはフェリパ・ペレストレリョ(ペレストレーロ[8])・エ・モイス(またはフェリパ・モニス・ペレストレロ[9])と結婚した。ロス・サントス修道院のミサで彼女を見初めたのがなれそめという[3]。しかし、フェリパの父はマデイラ諸島にあるポルト・サント島の世襲領主バルトロメウ・ペレストレリョ(ペレストレーロ)であり、いわば貴族階級の女性であった。この釣り合わない結婚の背景には、フェリパが25歳という、当時としては晩婚と言える年齢であったこと、父バルトロメウは20年前に死去し、以後のペレストレリョ家は没落しており持参金を準備できなかったこと、逆にコロンブスは航海士・地図製作者として一定の成功を収めていたことなどがあったと推察されている[8][9][10]。 結婚後は妻のゆかりの地ポルト・サント島(またはマデイラ島)に夫婦で行くこともあり、1480年ごろにそこで長男ディエゴに恵まれた。1481年、ディオゴ・デ・アザンプージャ
ポルトガル時代
リスボンでのコロンブス
西廻り航海の着想
また、当時のある事件をラス・カサスは『インディアス史』(第一巻十四章)に記している。それは、マデイラ島に漂着した白人漂流者がいたというものである。