El 25 de septiembre de 1493, zarparon las 17 naves, 5 naos y 12 carabelas, desde el puerto de Cádiz hasta La Gomera, a donde llegó el 5 de octubre. Compraron ganado que llevaron consigo y fue así cómo se introdujo nuevas especies en el Nuevo Mundo, como el cerdo, la gallina, la cabra y la oveja, así como simientes de plantas como el naranjo, el limonero, el melón y otros tipos de hortalizas.
En este segundo viaje le acompañarían personajes conocidos como Alonso de Ojeda, Juan de la Cosa, quien también iría en el del descubrimiento, y Juan Ponce de León.
El lunes 7 de octubre izaron las velas y el 3 de noviembre llegaron a una isla a la que llamó Dominica, por haberla descubierto en domingo. Al norte de ésta bautizó la isla de Marigalante, como la nao en la que iba, donde pisó tierra para tomar formalmente posesión. Continuaron hasta Guadalupe donde encontraron a nativos de otra isla (Boriquen) huyendo. Según decían, esta isla estaba habitada por caribes, nativos caníbales que cazaban presas en otras islas. Es decir, Colón había conocido dos tipos de razas, los arahucos, que era pacíficos y habitaban las islas más grandes, y los caribes, de los que oyó hablar en su primer viaje sin dar credibilidad. Eran tribus guerreras y antropófagas que cazaban para alimentarse.
Diego Márquez, capitán de un navío, bajó a tierra con 8 de sus hombres a explorar. Al no volver, Colón mandó algunas cuadrillas en su búsqueda, pero no lo encontraron. Decidió mandar un gran grupo de 40 hombres con Alonso de Ojeda, capitán de otro de los navíos, al mando, a explorar la isla en busca del grupo desaparecido. Sin embargo, tampoco tuvieron éxito. Finalmente, el primer grupo logró volver habiendo rescatado a 10 mujeres y niños de los caribes, que no se encontraban en la isla al haber salido a cazar.
El 10 de noviembre levantaron las anclas y fue poniendo nombre a las islas que iba descubriendo, Monserrate, Santa María la Redonda, Santa María la Antigua y San Martín. El 14 de noviembre llegaron a Santa Cruz donde tuvieron un enfrentamiento con nativos. Desde allí prosiguieron el viaje hacia La Española y llegaron a un grupo de islas, nombrando a la mayor de ellas Santa Úrsula y a las demás, las Once Mil Vírgenes. Desde allí llegó a la isla a la que bautizó con San Juan Bautista, que en indígena era Boriquen, y en la actualidad es Puerto Rico, donde bajaron a tierra pero sin encontrar a nadie. Como en otras ocasiones, los poblados estaban abandonados. Los nativos debieron huir al ver llegar los navíos.
Siendo ya el 22 de noviembre, llegaron a la isla de La Española y un indio del primer viaje salió en busca de los habitantes de allí para decirles que no había nada que temer, sin embargo desapareció y lo dieron por muerto.
Llegaron al fuerte Navidad, donde dejaron en el primer viaje a los 39 compatriotas, pero no quedaba más que una estructura quemada. Por lo que les contaron, al poco de partir Colón, empezaron a reñir entre ellos. Alguno acabó muerto y la avaricia de otros los llevó a rebelarse e internarse en tierras del cacique Caonabo, donde se suponía que estaban las minas de oro. Esto, unido a que se quedaron con mujeres de nativos, originó que el cacique matase a los rebeldes y que posteriormente fuera al fuerte para matar a Diego de Arana y los otros cinco que le habían sido fiel. A pesar de que el cacique Guacanagarí los trató de defender, nada pudo hacer. Incluso quedó malherido.
Colón partió de ahí en busca de un puerto natural más propicio para un asentamiento, encontrando hacia el este el sitio idóneo donde el 6 de enero de 1494 inauguró la primera población con el nombre de La Isabela, en honor a la reina Isabel.
Ese mismo mes envió a Ojeda con 15 hombres a explorar la región de Cibao, encontrando oro.
El primer mes del año fue especialmente duro para los colonos. Muchos cayeron enfermos e incluso murieron a causa del agotamiento, tanto por el viaje como por la construcción del poblado. El clima era muy distinto y requería cierta aclimatación. Además, los alimentos también escaseaban. Esto fue el inicio del desprecio hacia Colón por parte de los primero colonos.
El 2 de febrero de 1494 envió de vuelta a Castilla, 12 de las 17 embarcaciones con Antonio de Torres como capitán. En dicha expedición informó a los Reyes sobre los avances logrados y envió algunos papagayos, algo de oro y algunos indios caribes que tenían presos. Al mes siguiente tuvo que hacer frente a un intento de rebelión por parte de Bernal de Pisa. El hecho de que Colón no fuese castellano no gustaba a muchos de los colonos.
El mes de marzo lo empleó a explorar parte de la isla, descubriendo numerosos poblados y mandando construir diversos fuertes en ubicaciones estratégicas, cerca de minas de oro o bien tierras de labranza. A destacar la fortaleza Concepción en La Vega, que aún se mantiene parcialmente en pie. En el mes de abril, apareció el cacique Caonabo, a quien temían los lugareños, con intención de atacar el fuerte Santo Tomás. Colón mandó a Alonso de Ojeda con más de 400 hombres en su defensa y apresó al cacique Caonabo. Colón, temiendo que mantenerlo preso empeoraría las relaciones con los nativos, decidió liberarlo. Este sería el primer enfrentamiento con nativos en La Española después del suceso con los 39.
El 24 de abril de ese año, zarpó con una nao y dos carabelas hacia poniente para explorar, dejando a su hermano Diego al mando. Recorrió el sur de Cuba. Continuó hasta Jamaica para después seguir hacia el sur a la isla que nombró Evangelista (hoy isla de la Juventud). Desde allí continuó a Jamaica bordeándola por el sur para continuar hasta La Española y navegarla también por el sur hasta la isla Mona, situada en el extremo oriental y finalizar el 29 de septiembre de nuevo en La Isabela tras un trayecto de vuelta muy difícil por las tormentas que sufrieron y porque la dirección del viento no les permitía navegar en dirección al este.
Colón llegó enfermo y no se repuso hasta cinco meses después.
En el tiempo que estuvo ausente, había llegado su hermano Bartolomé desde España. También se desmadró el contingente del fuerte Santo Tomás con la huida de su capitán, que se volvió a España. Algunos hombres empezaron a abusar de los indios locales y a apropiarse de sus propiedades y mujeres. Esto llevó a ciertos ajusticiamientos por parte de los caciques locales.
Al considerar Colón que la pena de muerte había sido desproporcionada, mandó de nuevo a Alonso de Ojeda al interior de la isla, quien volvió con Caonabo y sus súbditos presos.
Caonabo fue embarcado para enviarlo a Castilla, pero antes de que zarpase el barco, un huracán hundió todas las embarcaciones en el mismo puerto, ahogándose entre otros, el cacique. Este suceso provocó el alzamiento de los demás caciques de la isla, salvo Guacanagarí, que seguiría siendo fiel a Colón. Se iniciaría una guerra entre los dos bandos.
Colón, virrey del Nuevo Mundo, envió diversas expediciones, destacando la de Francisco de Garay que llegó hasta el sur de la isla estableciendo las minas de San Cristóbal. En ese lugar, Cristóbal mandaría a su hermano Bartolomé la construcción de San Cristóbal, siendo ésta el germen de la actual ciudad de Santo Domingo.
El 10 de marzo de 1496 zarpaba en las dos carabelas que mandó hacer, con más de 220 colonos que querían retornar o enfermos en dirección a Castilla. Y el día 10 del mes siguiente, tras una navegación lenta y tediosa, hicieron escala en Guadalupe, donde se aprovisionaron de leña y comida para no dejar la Isabela sin recursos. Tras diez días continuaron el viaje que se alargó hasta el 11 de junio, cuando llegaron a Cádiz. Hay que destacar que por aquellas fechas aún no se había descubierto la latitud en la que era propicio el retorno, siendo cada trayecto muy peligroso.
Colón se trasladó rápidamente a Sevilla y desde allí a Burgos, donde se encontraba la Corte. Mientras se encontraba en España, se iniciaba la construcción del asentamiento de Santo Domingo, aunque él quería que se llamase Isabela Nueva. Casi todos los pobladores se trasladaron al nuevo asentamiento quedando atrás únicamente enfermos y unos obreros que estaban construyendo dos carabelas.
Tras esta visita a los Reyes, éstos creyeron oportuno crear una ruta periódica con las islas de ida y vuelta, llevando y trayendo mercancías, además de colonos y correspondencia.
