Kerrotaan Kolumbuksen jälleen vuonna 1488 pyrkineen Portugalin kuninkaan kanssa yhteyteen, mutta siitä ei liene tullut mitään, ei ainakaan tuloksiin johtavassa mielessä. Sanotaan tähän vaikuttaneen sen, että Bartholomeu Diaz oli juuri silloin palannut siltä matkalta, jolla hän oli löytänyt Hyväntoivonniemen ja päätellyt meritien Intiaan kulkevan sen kautta, eikä portugalilaisia kiinnostanut läntisen meritien löytäminen, mikä oli aivan epävarma.
Kolumbus palasi jälleen anomaan Espanjan hallituksen apua. Sitä hänelle ei kuitenkaan luvattu ennenkuin lokakuussa 1491. Huhtikuun 17. päivänä seuraavana vuonna allekirjoitettiin Espanjan hallitsijaparin ja Kolumbuksen välinen sopimus, ja saman kuun 30. päivänä satamakaupunki Palos sai tehtäväkseen asettaa Kolumbuksen käytettäväksi kaksi purjealusta. Se velvoitus aiheutui mainitun kaupungin asukkaiden tekemästä laiminlyöntirikoksesta vastapäättyneen, maureja vastaan käydyn sodan kestäessä. Kolumbus sai sittemmin vielä kolmannenkin laivan.
Kolumbus kävi Amerikassa kaikkiaan viisi eri kertaa, neljästi elävänä ja kerran ruumiina. Hänen ensimmäisen matkansa kuvailee tässä julkaistava päiväkirja.
Toiselle matkalleen hän lähti syyskuun lopulla 1493, ja silloin hänellä oli seitsemäntoista laivaa, joissa oli tuhatviisisataa henkeä, hevosia, siemenviljaa, viiniköynnöksiä ja muuta tavaraa uusiin maihin perustettavien siirtokuntien tarpeeksi. Kanarian saarilta matka valtameren ylitse kesti kaksikymmentä päivää.
Hänellä oli silloin mukanaan veljensä Diego Kolumbus, joka jäi Españolan saarelle perustetun Isabella-siirtokunnan ylipäälliköksi. Itse hän lähti saaren sisäosista etsimään kultaa ja löysikin kulta-alueen. Sitten hän purjehti Kuuballe ja Jamaikaan, mutta palasi sieltä huonossa kunnossa syyskuussa 1494 Isabellaan, jonne sillä välin oli tullut hänen toinenkin veljensä, Bartolomé, tuoden siirtokunnalle lisää muonaa, joka olikin sangen tarpeen, sillä espanjalaiset eivät pystyneet oudoissa oloissa tulemaan toimeen. Kristoffer Kolumbuksen ollessa matkalla osa väestöä oli alkanut niskuroida Diegoa vastaan, ja elämöiminen puhkesi lopulta ilmikapinaksi; niskuroitsijoiden anastaessa Bartolomén laivat ja lähtiessä Espanjaan kantelemaan kuningasparille Kolumbusta vastaan.
Mellastelevien espanjalaisten ilkityöt aiheuttivat kiistan saaren alkuasukkaiden kanssa, ja lähes satatuhantinen intiaaniarmeija kävi heidän kimppuunsa siitä huolimatta, että Kolumbus oli kaikin tavoin omalta osaltaan pyrkinyt rauhallisiin väleihin intiaanien kanssa. Intiaanit hävisivät taistelun, tuhannet saivat surmansa ja sotavangit otettiin orjiksi; viisisataa lähetettiin Sevillaan myytäviksi.
Espanjaan menneet niskurit saivat aikaan, että kuningaspari lähetti Españolaan luottamusmiehen tutkimaan saaren oloja, ja Kolumbus lähti itse Espanjaan antamaan selitystä. Hän sai kumotuksi häntä vastaan tehdyt syytökset helposti, vieläpä hänelle varustettiin laivastokin, kun hirmumyrsky oli Españolassa tuhonnut kaikki siellä olleet laivat paitsi sitä ainoata, jolla Kolumbus palasi Espanjaan.
Mutta kolmannelle matkalle ei riittänyt miehiä. Sota Ranskaa vastaan oli käynnissä, ja Kolumbus sai laivojensa väeksi maanpakolaisuuteen tuomittuja rikollisia, ja kuudella aluksella hän toukokuun 30. päivänä 1498 lähti kolmannelle matkalleen. Kanarian saarilla hän jakoi laivastonsa kahtia. Toinen osa purjehti suoraan Españolaan, toisella hän itse lähti eteläisempää tietä Kap Verden saarien kautta ja päätyi monen vastuksen perästä Etelä-Amerikan manterelle Orinoco-virran suun seuduille.
Hän ei kuitenkaan ryhtynyt tarkemmin tutkimaan uutta löytämäänsä maata, vaan kiirehti Españolaan, jossa asiat olivat taas hullusti. Siellä oltiin tyytymättömiä Bartolomé Kolumbuksen tiukkaan hallintoon, ja saaren ylituomari Roldan oli asettunut kapinallisten johtajaksi »mokomaa muukalaista» vastaan. Kristoffer Kolumbus saapui juuri silloin saarelle, antautui neuvotteluihin kapinallisten kanssa ja rauhan saavuttamiseksi suostui nöyryyttäviin ehtoihin.
Sillävälin panettelijat olivat Espanjassa tehneet työtä, ja tuloksena oli, että Españolaan lähetettiin uusi käskynhaltija Francisco de Bobadilla, joka perille tultuaan hankki itselleen joukkojen suosion antamalla kaikille kullankaivuuluvan, kun Kolumbuksen veljekset osuivat olemaan poissa. Näiden palatessa Bobadilla vangitsi Kolumbukset ja lähetti heidät kahleissa Espanjaan.