Marraskuun loppupuolella saavuttiin Espanjolan etelärannalle, mutta Columbus ei nyt joutanut sitä tutkimaan, vaan kiiruhti Navidadiin, jonka hän toivoi näkevänsä mitä parhaassa kunnossa ja täynnään koottuja rikkauksia. Huonoja enteitä olivat kuitenkin ruumiit, joita siirtokuntaa lähestyttäissä löydettiin rannalta ja jotka näyttivät. olevan espanjalaisten. Laivasto löysi siirtokunnan satamaan, mutta ei ketään tullut vastaanottamaan. Amiraali antoi ampua kaksi tervehdyslaukausta, mutta niihin ei saatu mitään vastausta. Muuan yksinäinen intiani lähestyi vihdoin veneellä soutaen ja toi Guacanagari kuninkaaltaan kaksi kultaista naamaria lahjaksi. Kun häneltä kysyttiin, miten linnassa asiat olivat, niin hän sanoi kaikkien, jotka olivat siihen jääneet, jaksavan hyvin. Mutta pian selvisi kamala totuus. Siirtokunta oli hävitetty, eikä ainoatakaan siihen jääneistä espanjalaisista ollut elossa sen kohtalosta kertomassa. Navidadin puinen linna oli poltettu perustuksiaan myöden. Sen puolustajain ruumiita myöhemmin löydettiin. Asukkaitten peittelevistä kertomuksista tulliin siihen vakuutukseen, että seudun hallitsija Guacanagari oli ollut osallisena muukalaisten tuhoamisessa, vaikka hyökkäyksen olikin suunnitellut eräs karibilaissukuinen päällikkö, joka asui saaren eteläosassa. Siitä huolimatta Columbus ei ottanut Guacanagaria vangiksi, koska hän tahtoi niin kauan kuin mahdollista elää asukkaitten kanssa hyvissä väleissä.
Isabella.
Mutta Navidadin paikka hylättiin. Kolmisen kuukautta etsittyään Columbus idempää löysi mieleisensä uuden paikan ja perusti siihen Isabella nimisen linnan ja kaupungin. Nykyisin ei Isabellasta ole jäljellä kuin vähän raunioita, sillä pian huomattiin, että seutu, samoin kuin Navidadinkin, oli epäterveellinen. Kolmasosa uusista tulokkaista tuota pikaa oli vuoteen omana ja amiraali itse muitten mukana, niin ettei hän moneen kuukauteen voinut edes päiväkirjaansa pitää. Troopillisen ilmaston vaarat olivat silloin vielä liian vähän tunnetut. Seutu oli erinomaisen hedelmällistä ja rikasta kaikenlaisista tuotteista, ja tähän ensi sijassa kiinnitettiin huomio. Maanasukkaat olivat uudessakin paikassa erittäin avuliaita ja taipuvaisia kristinuskoon, vaikk'ei heidän kieltään vielä paljoa ymmärrettykään. Vielä enemmän Columbusta ilahutti tieto kultapaikoista, joita muka oli 25—30 penikulman päässä rannikosta, Cibao nimisessä maakunnassa.
Tammikuussa 1494 kävi urhollinen Alonso Ojeda 15:n seuralaisen keralla kultamailla ja toi sieltä mukanaan puroista kerättyä kultahiekkaa. Tämä löytö suuresti elvytti Isabellan uutisasukkaitten mieliä. Samaan aikaan lähetettiin yhdeksän laivaa takaisin Espanjaan viemään pois semmoisia, jotka olivat sairastuneet, taikka jotka muutoin halusivat päästä kotimaahan. Laivain mukaan antamassaan kirjeessä Columbus ehdotti, että Länsi-Intiaan säännöllisesti lähetettäisiin laivoja viemään karjaa ja tuomaan takaisin ihmissyöjiä Karibeja, jotka muka kelpasivat orjiksi. Näillä orjilla suoritettaisiin siirtokunnan kustannukset. Hän ehdotti siis samaa menetelmää, jonka Henrik Purjehtija oli alkanut Guinean rannikolla. Mutta Columbus tahtoi kuitenkin säästää niitä alkuasukkaita, jotka näyttivät hyvällä taipuvan kristinuskoon ja osottivat lempeätä mielialaa.
Parannuttuaan kuumeesta ja tukahutettuaan erään kapinayrityksen Columbus itse lähti käymään sisämaassa kulta-alueella, 400 hevosmiestä ja sotilasta ynnä paljon ammattitaitoista työväkeä mukanaan. Rannikkovuoriston poikki, kautta troopillisen tiheikön raivattiin ensin tie; retkikunnan jalosukuisimmat nuorukaiset suorittivat työn ja tietä siitä sanottiin »hidalgojen portiksi». Vuoriston toisella puolella avautui ihana maisema, tasanko, jonka kautta virtasi jokia kuin hopeisia nauhoja, siellä täällä tummempia metsiköitä, ja tasangon toisella puolella korkea vuoristo, josta kulta saatiin. Asukkaat osottivat pitkin matkaa suurta vieraanvaraisuutta, tuoden vallottajille hedelmiä ja jamsia lahjaksi. Kultajoen rannalle rakennettiin pieni linna kunnaalle, jonka joki melkein sulki silmukkaan. Linnaan jätettiin viisikymmentä miestä kullanhuuhtojain suojaksi. Kolmatta viikkoa viivyttiin tällä retkellä. Kullan saalis oli niin tyydyttävä, että eräs retkellä ollut lääkäri siitä kirjotti: »Ei maailman alusta ole semmoista ihmemaata nähty, eikä semmoisesta kukaan lukenutkaan. Sieltä saadaan kultaa niin kosolta, että se on hämmästyttävää. Minua ehkä luullaan haaveilijaksi, mutta Jumala on todistajani, etten vähääkään liiottele.» Columbus luuli tätä paikkaa Salomonin Ofiriksi.
Mutta Isabellassa tekivät kuume ja muut taudit sillä välin tuhojaan, puute, kurjuus ja tyytymättömyys lisääntyivät. Kaikki olisivat halunneet nopeaan rikastua, harvat työtä tehdä. Kun siirtokunnan omat raivaukset eivät vielä mitään tuottaneet, niin pelättiin nälänhätää. Onneksi oli kuitenkin siemeneksi tuotua vehnää. Columbus retkeltään palattuaan rakennutti myllyjä ja jauhatti viljaa. Kaikkien, yksin pappienkin, täytyi olla työssä avullisina, mutta heistä, varsinkin Boil nimisestä munkista, Columbus siitä hyvästä sai katkeria vihamiehiä. Vähentääkseen siirtokunnassa elätettävien lukua ja samalla ylläpitääkseen virkeämpää mielialaa Columbus lähetti 400 miehen joukon saarta eri osista tutkimaan. Saatuaan siirtokunnan asiat alulle, hän sitten valmistautui jatkamaan löytöretkeään. Isabellaa hallitsemaan jäi valiokunta, jonka esimies oli hänen nuorempi veljensä Diego.
Columbus jatkaa löytöretkeään.
Oli huhtik. 24 p. 1494, kun Columbus nosti ankkurin ja uudelleen käänsi keulan kohti tuntematonta länttä, kolme karavelia mukanaan. Hän saattoi paremmalla luottamuksella kuin ensi kerralla lähteä Cipangua ja Kataita etsimään, kun samalla puolen merta nyt oli satama, johon hän saattoi tarpeen tullen palata.
Purjehdittiin Espanjolan ja Cuban välisen salmen poikki Cuban etelärannalle. Sielläkin asukkaat olivat ystävällisiä ja kutsuivat Columbusta maihin vieraakseen. Guanahanista otetun luotsin kehotuksesta amiraali sitten ohjasi etelää kohti etsimään suurta saarta, josta Cuban asukkaat olivat kertoneet. Siten hän tuli Jamaicaan, jonka verraton luonto teki häneen syvän vaikutuksen. Saari sai nimekseen Santiago; amiraali nousi upseereineen maalle ja otti sen Espanjan kruunun omaksi. Mutta asukkaat olivatkin vihamielisiä ja hyökkäsivät retkikunnan kimppuun; he kääntyivät kuitenkin nopeaan pakoon, kun amiraali käski ampua arkipuuseilla. Jonkun ajan kuluttua he taas palasivat takaisin ja solmittiin rauha. Retkikunta saattoi häiritsemättä kallistaa laivat ja puhdistaa niitten pohjat. Purjehdittiin sitten Jamaican pohjoisrantaa saaren länsipäähän, seurana seitsemänkymmentä suurta kanottia. Mutta kun vastatuulet estivät purjehtimasta edemmäksi etelää kohti, niin palattiin Cubaan ja jatkettiin matkaa länteen päin pitkin sen etelärantaa.
Tämä purjehdus oli sangen vaikeaa ja vaarallista, sillä Cuban etelärannalla on lukemattomia pieniä saaria ja luotoja, jotka vaativat ainaista valppautta. Kun saaria oli niin taajassa, ettei niille olisi jokaiselle nimeäkään riittänyt, niin amiraali nimitti ne yhteisellä nimellä »Kuningattaren puutarhaksi»; toiset olivatkin kuin kukka- ja vihanneslavoja uhkuvine metsineen, köynnöskasvineen ja kukkivine puineen. Ulompana merellä olisi väylä ollut selvempi, mutta Columbus tahtoi pysyä maassa kiinni, sillä juuri tämä saarisokkelikko hänelle vakuutti, että Intian ja Katain manner oli lähellä; semmoinen saaristo juuri piti Toscanellin ja muitten kosmografien karttain mukaan olla Intian kaakkoisrannikolla.