Miastu Palos rozkazano wystawienie dwóch karawel z załogami, które przez trzy miesiące miały być w dyspozycji Kolumba. Były to nieduże okręty „Nina” i „Pinta”. Rekrutacją załóg zajęli się ich kapitanowie: Martin Alonso i Vincente Yanez Pinzonowie, którzy zwerbowali 48 marynarzy. Flaga admiralska zawisła na niedużej karace „Santa Maria” z 43-osobową załogą, dowodzonej przez Juana de la Cosę.

Wyremontowane i zaprowiantowane na rok okręty opuściły Palos 3 sierpnia 1492 roku, kierując się ku Wyspom Kanaryjskim. Po uzupełnieniu tam wody i drobnych naprawach 8 września mała armada popłynęła na zachód wzdłuż 28 równoleżnika szerokości geograficznej północnej, będącego granicą portugalskiej strefy wpływów. Po kilkunastu dniach osiągnięto Morze Sargassowe, tj. ogromną masę nagromadzonych pośrodku Atlantyku wodorostów, które poważnie utrudniły żeglugę. Przedłużająca się podróż tak przerażała załogi, iż w obawie przed buntem Kolumb w dzienniku okrętowym notował odległości dzienne mniejsze od rzeczywiście pokonywanych.

Już jednak 7 października żeglarze zorientowali się, że w pobliżu jest ląd. Wskazywały na to przelatujące stada ptaków. Mimo to marynarze głośno domagali się powrotu, a na „Santa Marii” około 10 października wybuchł bunt. Niech wasza miłość każe powiesić z pół tuzina – radził Kolumbowi Alonso Pinzon – albo wrzucić do morza, a gdyby waszej miłości zabrakło odwagi ja i moi bracia zwiążemy ich liną kotwiczną i wypchniemy za burtę, gdyż armada, która wypłynęła z polecenia Królewskich Mości, nie może wszak powrócić bez dobrych nowin. Admirałowi udało się uśmierzyć rebelię bez użycia siły, 12 października (po 33 dniach żeglugi) o godzinie drugiej w nocy stojący w bocianim gnieździe Rodrigo de Triana dostrzegł ląd. Nie otrzymał jednak obiecanej za to przez królów katolickich nagrody (10 tys. marawedów), bowiem Kolumb bezprawnie ją sobie przywłaszczył.

Lądem okazała się wysepka Guanahani położona w archipelagu Bahamów, którą Kolumb nazwał San Salwador. Uczeni spierają się, czy chodzi o dzisiejszą wyspę Watling, czy raczej o leżącą 130 km dalej Samana Cay. Pierwszy kontakt z mieszkańcami wyspy Indianami Arawakami, był zaskakująco serdeczny. Witali oni przybyszów jak bogów i oddawali im wszystko co mieli. Niestety byli bardzo biedni: nie posiadali ani korzeni ani licznych wyrobów ze złota.

Ujrzeli niebawem nagich ludzi – relacjonował kronikarz hiszpańskiej konkwisty i obrońca tubylców Bartolomeo Las Casas Admirał dobił do brzegu na dobrze uzbrojonej szalupie, a wraz z nim jednocześnie Martin Alonso Pinzon i brat jego Vicente Yanez Pinzon, kapitan Niny. Admirał rozwinął sztandar królewski, a dwaj kapitanowie chorągwie Zielonego Krzyża, które admirał przyjął jako znak rozpoznawczy dla każdego ze statków... Wysiadłszy na ląd ujrzeli drzewa bardzo zielone, liczne strugi wodne oraz owoce rozmaitego rodzaju. Admirał przywołał obu kapitanów oraz innych ludzi załogi... zażądał od nich, aby uznali i potwierdzili legalne objęcie w posiadanie tej wyspy wobec wszystkich obecnych.