Hän ilmoitti ajatuksensa ensin Portukalin kuninkaalle Johan II:lle, joka niistä kysyi asiantuntijain mieltä ja sitte jätti ne ilman huomiotta. Silloin Kolumbus siirtyi Espaujaan. Siellä hallitsi Aragonian kuningas Ferdinand yhdessä puolisonsa Kastilian kuningattaren Isabellan kanssa; molemmilla oli siihen aikaan tekemistä sodassaan Granadan valtakuntaa vastaan. Kauan kesti ennenkuin Kolumbus edes pääsi Ferdinandin puheillekaan. Kuningas ensin asetti oppineita miehiä tutkimaan genualaisen aietta. He tekivät monta väitöstä sitä oletusta vastaan, että asuttua maata olisi päinvastaisella maanpuolikkaalla. Kuinkahan osaisivat, arveli monikin viisaudessaan, ihmiset astua päälaellaan niinkuin kärpäset katossa? Kolumbuksen aietta siis hyvin huonosti kannatettiin.
Avutta ja neuvottomana tapasi Kolumbus nyt kokeneen merimiehen Alonzo Pinzonin, joka innolla ryhtyi yritykseen. Ilojuhlia vietettäessä Granadan valloituksen johdosta kääntyi hän uudella toivolla kuningatar Isabellan puoleen ja antoi uuden anomuksen. Tällä kertaa otettiin hänet suosiollisemmin vastaan; mutta hovi ei hyväksynyt hänen asettamiansa ehtoja. Hän aikoi silloin heti lähteä puhutteleman Ranskan kuningasta. Mutta kuningatar muutti mielensä; jäljestä lähetetty ratsumies tapasi Kolumbuksen ja sai hänet palaamaan. Hän oli tinkinyt itselleen aatelisarvon, Indian amiraalin arvon ja kaikkien maiden varakuninkaan arvon, jotka hän ehkä löysi, sekä kymmenennen osan niiden maiden kruununtuloista.
Ensimmäinen matka. Nyt varustettiin kolme pientä laivaa, joista kaksi tuskin oli muuta kuin purjeveneet. Mutta väkeä oli vaikeampi saada matkalle, koska reippaimmatkin merimiehet pelkäsivät niin uhkarohkeaa yritystä. Viimein ilmoittautui kolme Pinzon-veljestä, jotka olivat tehneet monta merimatkaa ja joilla oli palveluksessaan paljo merimiehiä; he myöskin tarjoutuivat itse panemaan kahdeksannen osan kustannuksista.
Elokuun 3 päivänä 1492 vähän ennen auringon nousua läksivät nämä kolme laivaa merelle pienen Palos-kaupungin luota Andalusian rannasta. Kolumbus itse johti suurinta alusta "Santa Mariaa", toista johti Alonzo Pinzon ja kolmatta, kaikkein pienintä, hänen veljensä Vincent Pinzon. Kanariansaarissa käytiin korjaamassa yhtä alusta, jonka peräsin oli rikkautunut. Lähes kuukauden viivyttyään siellä purjehtivat Kolumbus ja hänen kumppaninsa aukealle merelle suoraan länttä kohti. Jo seuraavana päivänä oli kaikki maa kadonnut näkyvistä; ei miltään taholta näkynyt mitään muuta kuin sinitaivas ja aava meri, jonka syvyyden päällä heikot alukset uiskentelivat. Yhä etemmäksi taakse jäi kaikki, kuin ihmissydämmelle on rakasta, isänmaa, sukulaiset ja ystävät; edessä oli kaikki hämärää ja salaperäistä. Moni karaistunut merimies itki ja muutamat valittivat ääneensä. Kolumbus koetti kaikin tavoin lievittää huolia ja väestössä herättää samaa suurta toivoa, kuin häntä itseään elähytti. Eräänä iltana Alonzo Pinzon viittasi lounatta kohti ja huusi sieltä näkyvän maata. Purjehdittiin purjehtimistaankin sinne päin, mutta ei mitään maata ruvennut näkymään. Suunnan käännöksestä jouduttiin Golf-virtaan ja laivat juoksivat sitte aika vauhtia eteen päin. Merimiehet vapisivat tuskaisesta levottomuudesta, kun ei kukaan heistä tiennyt, mihin tuollaista vauhtia viimein jouduttiin.
Suotuisia merkkejä ilmestyi ja hävisi. Nähtiin tuntemattomia lintuja; mutta ne eivät ennustaneet maata, koskapa merilinnut saattavat lennellä kauempanakin, kuin silloin tiedettiin. Kerran oli koko merenpinta ruohon peitossa; moni merimies, jopa Kolumbus itsekin silloin luuli maan olevan lähellä. Kun toivo moneen kertaan pettyi, alkoivat merimiehet joutua epätoivoon. He alkoivat jo puhua, että he eivät halunneet purjehtia etemmäksi, että heidät oli houkuteltu retkelle, joka ei suinkaan voinut onnistua, ja että he tahtoivat kääntyä, kun vielä voivat toivoa pääsevänsä takaisin kotimaahan.
Kristofer Kolumbuksen laiva. (Vanhan piirustuksen mukaan.)
Mutta kohta rupesi näkymään ihan selviä maan läheisyyden merkkejä. Maalintuja laskeutui mastoihin levähtämään ja puunoksa, jossa oli punaisia marjoja, uiskenteli lännestä päin vastaan. Kello kymmenen eräänä iltana huomasi Kolumbus pienoisen valon tuikkavan etäällä lännessä päin. Noin kello kaksi kuului Alonzon laivasta, joka tavallisesti purjehti vähän matkan päässä toisten edellä, kanuunan laukaus; se oli merkkinä, että maa oli saatu näkyviin. Ihastuksella huusivat kaikki: "Maa, maa näkyy!"
Lokakuun 12 päivänä aamun valjetessa levitti palmumetsäinen saari känniin vihreytensä purjehtelijain eteen. Ensimmäisen ilon ilmausten vaiettua veisasi koko väestö kiitosvirren.
Auringon noustessa asettui laiva ankkuriin ja suuri vene laitettiin valmiiksi. Amiraali pukeutui silloin tulipunaiseen virkapukuunsa ja sousi maalle Pinzon-veljesten ja monen muun seurassa, jotka kaikki olivat loistaviin varuksiinsa pukeutuneet. Astuttuaan maalle heittäytyi Kolumbus alas, suuteli maata ja otti sen Kastilian kruunun omaksi. Hän nimitti saaren San Salvadoriksi (vapahtajaksi), vaan sai sittemmin kuulla asujanten nimittävän sitä Guanahaniksi: se kuului siihen saaristoon, jota nyt sanotaan Bahama-saariksi.