Pasó a la historia de América por dar nombre a Venezuela, junto a Américo Vespucio, y por haber descubierto el lago Maracaibo, fundando a su vez Santa Cruz (La Guajira) en la actual Colombia. En sus dos primeros viajes, Juan de la Cosa pudo representar gran parte de las costas atlánticas de América en un Mapamundi, quedando expuesto que el Nuevo Mundo era un continente diferente.
El hecho de ser pariente de un compañero de oficio de Juan Rodríguez de Fonseca, obispo de Badajoz, fue aprovechado por Ojeda para conseguir su protección y promoción. Fonseca llegaría a ser presidente de la Junta de Indias, y como rival que era de Cristóbal Colón, vio en Ojeda un militar con valentía y experiencia, capacitado para hacer frente al almirante genovés en sus aspiraciones de dominación colonial. Por este motivo, Fonseca permitió a Ojeda embarcarse en el segundo de los Viajes Colombinos, rumbo al recién descubierto Nuevo Mundo, en septiembre de 1493.
El cacique Caonabó emprendió varios ataques al fuerte Santo Tomás y a la villa La Isabela, sin llegar a someter o poner en huida a los colonizadores. Incluso, el líder cigüayo fue apresado en un contrataque que dirigió Ojeda al campamento indígena.
La reacción de los indígenas de Cibao generó la batalla de la Vega Real, también llamada Jáquimo. Por la fuerza de las cargas a caballo que aterrorizaron a los guerreros cigüayos, Ojeda recibió el apodo de Centauro de Jáquimo.
La noticia de la captura de Caonabó en toda la isla supuso que se estableciese una alianza militar de todas las tribus indias de la isla, y lanzasen un ataque contra la villa La Isabela. El nuevo cacique cigúayo era Maniocatex, hermano del anterior, reunió a más de diez mil guerreros que se enfrentaron a unos cuatrocientos soldados españoles. Lo que parecía el fin de estos en La Española, se convirtió en una breve batalla. Años después, Bartolomé de las Casas escribió en su crónica de las Indias de forma exagerada que Ojeda había abatido a los diez mil gurreros indios con tan solo media docena de soldados españoles. Tras aquella gesta, en 1496, Ojeda regresaba a España.
Los llamados Viajes Andaluces o Viajes Menores dieron un nuevo impulso al descubrimiento, colonización y conquista de América, consiguiendo reconocer, en tan solo cuatro años, casi toda la costa atlántica de América central y sur. Estos viajes fueron comandados en diferentes expediciones por los hermanos Cristóbal y Luis Guerra, Rodrigo de Bastidas, Pedro Alonso Niño, Vicente Yáñez Pinzón, Diego de Lepe y otros.
El 18 de mayo de 1499, partía desde el gaditano Puerto de Santa María la primera de las expediciones andaluzas no comandada por Cristóbal Colón. Estaba promovido por el obispo Fonseca, rival de Colón, al que le había despojado de sus derechos de exclusividad en la colonización. Ojeda tenía el objetivo de comprobar la veracidad de los informes de Colón sobre las riquezas y extensiones territoriales de sus hallazgos, por petición de los Reyes Católicos. Estaba acompañado del cartógrafo Juan de la Cosa y el navegante Américo Vespucio.
Durante el trayecto bordeando la costa occidental africana hasta Cabo Verda, la flota se separó. Mientras que Vespucio lo hizo en dirección al actual estado de Brasil, Ojeda puso rumbo hacia el mar Caribe, hasta que alcanzó las desembocaduras de los ríos Esequibo y Orinoco, así como el golfo de Paria, las penínsulas de Paria y Araya, y las islas de Trinidad y Margarita.
Después siguió a lo largo de tierra firme por costas cumanesas, pasando luego por el cabo Codera, la Vela de Coro, el cabo de San Román y la isla de Curazao, que fue llamada isla de los Gigantes. También hizo la visita a la isla de Aruba y el archipiélago de los Frailes, siempre con el objetivo de encontrar un pasaje que le llevase al otro lado del territorio, en aguas inexploradas y de ahí poner rumbo a la Asia.
El 18 de mayo de 1499, partía desde el gaditano Puerto de Santa María la primera de las expediciones andaluzas no comandada por Cristóbal Colón. Estaba promovido por el obispo Fonseca, rival de Colón, al que le había despojado de sus derechos de exclusividad en la colonización. Ojeda tenía el objetivo de comprobar la veracidad de los informes de Colón sobre las riquezas y extensiones territoriales de sus hallazgos, por petición de los Reyes Católicos. Estaba acompañado del cartógrafo Juan de la Cosa y el navegante Américo Vespucio.
Durante el trayecto bordeando la costa occidental africana hasta Cabo Verda, la flota se separó. Mientras que Vespucio lo hizo en dirección al actual estado de Brasil, Ojeda puso rumbo hacia el mar Caribe, hasta que alcanzó las desembocaduras de los ríos Esequibo y Orinoco, así como el golfo de Paria, las penínsulas de Paria y Araya, y las islas de Trinidad y Margarita.
Después siguió a lo largo de tierra firme por costas cumanesas, pasando luego por el cabo Codera, la Vela de Coro, el cabo de San Román y la isla de Curazao, que fue llamada isla de los Gigantes. También hizo la visita a la isla de Aruba y el archipiélago de los Frailes, siempre con el objetivo de encontrar un pasaje que le llevase al otro lado del territorio, en aguas inexploradas y de ahí poner rumbo a la Asia.
En agosto de 1499, la exploración conjunta pasó a reconocer parte de la península de Paraguaná y el golfo de Venezuela. Este nombre, que significa Pequeña Venecia, fue dado por Américo Vespucio debido a que junto a la orilla vivían indígenas en casas sobre el agua, sostenidas con troncos, de igual parecido que ocurría en la Venecia renacentista. Después, la expedición encontró la entrada del lago Maracaibo, bautizada con el nombre de San Bartolomé. Y, por último, llegó hasta el cabo de la Vela, en la península de la Guajira, que fue llamada Coquibacoa.
Pero sería su compañero Américo Vespucio quien consiguió más repercusión en la historia. Fue el encargado de informar en la Corte española y en la Junta de Indias que las tierras descubiertas por Cristóbal Colón no pertenecían a Asia, sino que formaban parte de una cuarta parte del mundo a la que daría nombre de forma involuntaria.
Aquellas novedosas revelaciones fascinaron al cosmógrafo alemán Martin Waldseemüller, quien incluyó en su Cosmographiae Introductio las cartas de Vespucio, en 1507. Esta obra contenía los retratos de Ptolomeo y Vespucio, y en su prefacio escribió:
"Ahora que esas partes del mundo han sido extensamente examinadas y otra cuarta parte ha sido descubierta por Américo Vespucio, no veo razón para que no la llamemos América, es decir, tierra de América, su descubridor, así como Europa, África y Asia recibieron nombres de mujeres."De esta manera, el nombre de América se popularizó en toda Europa, quedando así bautizado el Nuevo Mundo. Un hecho algo incomprensible, cómo un protagonista secundario de origen italiano puede dar nombre al continente gracias a un alemán que jamás visitó América.
Según el historiador estadounidense Charles F. Lummis en su obra Exploradores españoles en el siglo XVI:
"Vespucio no tuvo la menor participación en los verdaderos descubrimientos del Nuevo Mundo. La historia está llena de injusticias; pero nunca se ha cometido otra mayor que ese bautismo de América. El primer mapa del Nuevo Mundo lo hizo el español Juan de la Cosa, en 1500, y ese mapa le parecía hoy raro a cualquier chico de escuela. La primera geografía de América, que data de 1517, se debe a Enciso, un español."
En enero de 1502, zarpaba la expedición formaba por cuatro carabelas, realizando el mismo itinerario que el anterior. Esta vez no hizo escala en el golfo de Paria y finalizó en isla Margarita. Después, recorrió las costas venezolanas desde Curiana hasta la península de Paraguaná. El 3 de mayo, fundó un asentamiento en la península de la Guajira, exactamente en bahía Honda, a la que llamó Santa Cruz, que se convirtió en el primer poblado español en territorio colombiano y, por tanto, el primero en tierra firme. Esta villa se convirtió en el primer poblado español en contar con cabildo y fortaleza en territorio firme continental, pero la segunda de la región de Sudamérica después de la actual ciudad sumergida Nueva Cádiz de Isla Cubagua, en el estado venezolano de Nueva España.
Sin embargo, Ojeda iba a sufrir una serie de problemas. Primero, los expedicionarios debían defenderse de continuos ataques que las tribus indias de la zona les lanzaban. Además, Ojeda mantenía disputas personales con sus hombres, hasta que sus socios Vergara y Campos decidieron apresarle, poco después de haber fundado Santa Cruz.
Esta segunda expedición resultó un fracaso, ya que no se habían descubierto nuevas tierras y no obtuvieron prácticamente riquezas. Además, el asentamiento Santa Cruz fue abandonado, y la gobernación de Coquibacoa fue abolida.
Desde mayo de 1502 hasta 1504, Ojeda estuvo preso en La Española. Mediante una apelación del obispo Rodríguez de Fonseca, pudo ser liberado, aunque pagando una cuantiosa indemnización que lo dejó bastante empobrecido. Durante los cuatro años siguiente permaneció en la isla.
En 1508, Ojeda se ofreció voluntario a la llamada del rey Fernando el Católico. Había promovido a concurso la gobernación y colonización de tierra firme, un espacio que abarcaba las tierras entre el cabo Gracias a Dios, situado entre los actuales estados de Honduras y Nicaragua, y el cabo de la Vela, situado en Colombia. Juan de la Cosa marchó a la Corte en representación de Ojeda. También apareció a concurso Diego de Nicuesa, en clara rivalidad por las aspiraciones de Ojeda. Como ambos candidatos tenían una buena reputación, la Corona decidió dividir el territorio en dos gobernaciones: Veragua al oeste y Nueva Andalucía al este, con límites en el golfo de Urabá.
Mediante la capitulación de 6 de junio de 1508, Ojeda recibía la gobernación de Nueva Andalucía; y Nicuesa la de Castilla de Oro (Veragua). Juan de la Cosa concretó que el límite exacto entre ambas gobernaciones sería el río Atrato, que desemboca en dicho golfo de Urabá.
El 10 de noviembre de 1509, Ojeda partía desde el puerto de Santo Domingo al mando de una expedición formada por trescientos hombres en dos bergantines y otros dos barcos pequeños.
Se sumaría al proyecto colonizador el geógrafo y abogado Martín Fernández de Enciso, quien llegaría en un viaje posterior con más provisiones y hombres para reforzar la colonización en las ciudades que se iban a fundar. A cambio esta ayuda, Ojera le permitió ocupar el cargo de alcalde mayor de la nueva gobernación. Antes de salir, el abogado hizo redactar al escribano Juan López de Palacios Rubios una meticulosa proclamación por la que persuadía a los indígenas a formar parte del Imperio español y guardar fidelidad a la Corona de forma voluntaria, y cuya negación conllevaría represalias por la fuerza.
Ojeda llegó a la bahía de Calamar, en la actual ciudad colombiana de Cartagena. Pretendía tomar posesión de las tierras aledañas enviando a unos misioneros religiosos para que realizaran la proclamación frente a un grupo de indígenas, acompañados de intérpretes nativos. Después, ofreció un intercambio comercial. Y el resultado final fue un enfrentamiento con huida de los indios.
Tras llegar a la aldea de Turbaco, los indios lanzaron de nuevo otra ofensiva en la que murieron gran número de expedicionarios. Entre los caídos estaba Juan de la Cosa, quien sacrificó su vida para que Ojeda escapara. El gobernador consiguió llegar a la playa y ser rescatado por la flotilla anclada en la bahía. Pocos días después, fueron alcanzados por la flota de Diego de Nicuesa, mucho más numerosa en cuanto efectivos. Tras olvidar las diferencias entre ambos gobernadores, se unieron para emprender un ataque conjunto a Turbaco, que fue arrasada.
Con una pequeña flota sobreviviente reforzada con algunos hombres y armadas comprados a Nicuesa, Ojeda continuó su proyecto colonizador de la gobernación de Nueva Andalucía hacia el suroeste.
El 20 de enero de 1510, fundó el enclave llamado San Sebastián de Urabá, en el golfo de Urabá. Tras ocho meses y medio de exploración, el fuerte allí construido sufrió un durísimo ataque de los indios urabaes de la zona. Ojeda fue herido en una pierna por una flecha envenenada, y la situación de los resistentes era insostenible por la falta de alimentos y el ambiente insalubre. Esperaba que llegara la flota de Enciso que prometió enviar. Ante la tardanza, Ojeda decidió ir a por ellos a Cartagena de Indias.
En sustitución, dejó a un joven soldado extremeño llamado Francisco Pizarro, quien años más tarde conquistaría el Reino incaico del Perú. Se le encomendó defender el fuerte de San Sebastián junto a unos setenta soldados y colonos durante cincuenta días hasta su posterior regreso. Si esta condición no se cumplía, todos los supervivientes tenían licencia para regresar a Santo Domingo a bordo de los dos bergantines.
Por fin llegaron los refuerzos de Fernández de Enciso al fuerte de San Sebastián, al mando de una carabela y un bergantín. Estaba acompañado de un polizón llamado Vasco Núñez de Balboa, quien poco más tarde descubriría el océano Pacífico atravesando el istmo de Panamá. Ambos encontraron un lamentable fuerte y a unos defensores desesperados por el hostil cerco efectuado por los urabaes.
Tras socorrer a los pocos supervivientes de Pizarro, fueron embarcarlos y trasladados al otro lado del golfo, por orden de Balboa. Allí los indios eran más dóciles, y pudieron fundar Santa María la Antigua del Darién, excluida de la gobernación de Diego de Nicusia. Estaban incumpliendo la división entre gobernaciones establecida por De la Cosa, pues la nueva villa estaba justo en la orilla oeste del río Atrato, que era territorio de Castilla de Oro.
Desde Cartagena, Ojeda había huido en el bergantín de un pirata español llamado Bernardino de Talavera, que trató de refugiarse ante la orden en su búsqueda y captura por las autoridades virreinales de La Española. Durante el trayecto, la embarcación naufragó en Jagua, Sancti Spíritus, al sur de Cuba, debido al arrastre que ejerció un temporal. Desde allí, recorrieron la costa sur de la isla caminando hasta punta Maisí. Allí fueron recogidos por Pánfilo de Narváez, desde donde navegaron hasta Jamaica. Entonces, Talavera fue detenido por practicar la piratería y Ojeda se enteró de la llegada de la flota de Enciso.
Tras este fracaso, Ojeda renunció a su cargo de gobernador de Nueva Andalucía y no volvió a dirigir ninguna otra expedición. Pasó los últimos cinco años de su vida en Santo Domingo, hasta que se retiró al Monasterio de San Francisco, donde murió, en 1515.
En 1936, el presidente de la República de Venezuela, Eleazar López Contreras, puso el nombra a Ciudad Ojeda en reconocimiento al explorador español por haber descubierto el lago de Maracaibo y dar nombra a Venezuela.
Las aventuras del primer gobernador de Nueva Andalucía se han llevado a la novela por Vicente Blasco Ibáñez, en su obra El caballero de la Virgen, publicada en 1929; y por Alberto Vázquez-Figueroa, en su obra Centauros, en 2007.