In april 1493 te Palos geland, kreeg hij nu in Spanje volledige steun voor een nieuwe expeditie: er werden 17 schepen met 1500 man uitgerust. Men stak in zee op 25 sept. 1493 te Cádiz; Columbus voer via de Canarische Eilanden meer in zuidelijke richting en ontdekte op 3 nov. Dominica. Hij koerste daarna noordwestwaarts en verkende de meeste eilanden van de Kleine Antillen. Via Porto Rico kwam hij naar Haïti en stichtte er een nieuwe nederzetting, die hij Isabella noemde. De kolonisten ondervonden grote moeilijkheden met de inboorlingen, legden hiervan alle schuld bij Columbus en beschuldigden hem bij de koningin. In juni 1495 keerde hij naar Spanje terug en slaagde erin zijn reputatie te herstellen. Het duurde tot 1498 voor hij voldoende kapitaal had om een derde reis te ondernemen.