W poszukiwaniu złota okręty rozdzieliły się, a Kolumb z „Santa Marią” i „Niną” 5 grudnia dopłynął do Haiti (nazwanej Hispaniolą). Znaleziono tu więcej wyrobów ze szlachetnych kruszców oraz nawiązano handel wymienny z tubylcami. W nocy z 24 na 25 grudnia „Santa Maria” osiadła jednak na rafie w zatoce Navidad i trzeba było ją opuścić. Kolumb zdecydował wybudować tu fort Villa de la Navidad. Pozostało w nim 39 uczestników wyprawy, którzy mieli skupować złoto od Indian i zbadać wyspę. Natomiast sam admirał na pokładzie „Niny” ruszył 16 stycznia 1493 roku w podróż powrotną. Po drodze okręty natrafiły na bardzo trudne warunki pogodowe i cudem uniknęły utonięcia. Ostatecznie 3 marca osiągnięto ujście Tagu, a dwanaście dni później okręty weszły do Palos. Odkrycie drogi powrotnej z Ameryki Środkowej do Europy należy uznać za jedno z największych osiągnięć Kolumba.
Powitanie „zdobywców Indii” w Barcelonie było uroczyste. Admirał wszedł na podwyższenie, na którym znajdowali się królowie otoczeni przez mnóstwo kawalerów i znaczniejszych osób, o pośród nich zdał się być rzymskim senatorem – informuje Las Casas. Szlachetna była jego twarz, szlachetna była jego siwizna, szlachetny był jego uśmiech, skromny i radosny, w którym odbijała się sława jego niezwykłego czynu. Królowie katoliccy raz jeszcze potwierdzili dziedziczne tytuły wielkiego admirała i nadali mu szlachectwo. Uzyskał jurysdykcję na terenach położonych na zachód od Wysp Kanaryjskich i Wysp Zielonego Przylądka oraz prawo wyrażania zgody na wyprawy do Indii.
Powodzenie pierwszej peregrynacji sprawiło, że kolejna handlowo-wojskowa ekspedycja wyruszyła z Kadyksu już 25 września 1493 roku. Wzięło w niej udział 17 okrętów i blisko 1500 ludzi. Flagowym statkiem była teraz „Marie Galante”, zaś do Ameryki popłynęli z nim m.in. Alonso de Hojeda i ponownie Juan de la Cosa. Obrany kurs, nieco bardziej na południe od poprzedniej trasy, dzięki sprzyjającym wiatrom okazał się wyjątkowo korzystny i już 3 listopada hiszpańska flota dotarła do wyspy Dominiki w archipelagu Małych Antyli. Niebawem Kolumb odkrył kilkadziesiąt wysepek tego archipelagu (m.in. Gwadelupę) oraz Puerto Rico, a także stoczył pierwsze potyczki z tubylcami – Karaibami.
27 listopada Hiszpanie dotarli do Hispanioli, gdzie odnaleźli szczątki fortu Navidad, którego załoga została wymordowana przez Indian. Admirał nakazał zbudować nowe osiedle, osadę La Isabela oraz rozpocząć poszukiwanie złota na Hispanioli. Mimo niezadowolenia wielu uczestników szlacheckiego pochodzenia zmuszonych do pracy fizycznej oba przedsięwzięcia zakończyły się sukcesem. Niebawem Kolumb odesłał 12 okrętów do metropolii, a sam zaczął penetrować wyspy Wielkich Antyli. Pomiędzy kwietniem a końcem września 1493 roku ponownie dotarł do Kuby, odkrył Jamajkę i południowe wybrzeża Hispanioli.
Bezwzględność Hiszpanów wobec tubylców spowodowała wybuch powstań na Hispanioli, które brutalnie spacyfikowano. Zatargi i walki pomiędzy hiszpańskimi osadnikami, pogarszający się stan zdrowia, a także obawa o intrygi i utratę wpływów na dworze sprawiły, iż ostatecznie w marcu 1496 roku Krzysztof przekazał zarząd kolonii swemu starszemu bratu Bartłomiejowi (który założył najstarsze dziś miasto europejskie w Ameryce – Santo Domingo) i wyjechał do Kastylii. Trudna trzymiesięczna podróż, w trakcie której z głodu i chorób zmarła większość załóg i indiańscy niewolnicy, zakończyła się w Sewilli 11 czerwca 1496 roku. Mimo braku wyraźnego sukcesu finansowego nie można nie docenić osiągnięć tej wyprawy. Odkryła ona najdogodniejszą trasę z Europy na Morze Karaibskie, przyczyniła się do lepszego poznania Wielkich i Małych Antyli, zapoczątkowała konkwistę w Nowym Świecie.
