El 18 de mayo de 1499 parten del Puerto de Santa María en Cádiz las primeras naves descubridoras no comandadas por Cristóbal Colón. Esta expedición que supuso el fin de la exclusividad de Colón de organizar viajes de exploración fue promovida por Rodríguez de Fonseca para comprobar la veracidad de lo anunciado por Colón en sus cartas a los Reyes Católicos narrando los descubrimientos de su tercer viaje, también al llevar a Juan de la Cosa se tenía la intención de realizar el primer mapa de las costas de las nuevas tierras descubiertas.
La flota estaba compuesta por las carabelas Capitana y Nueva, la primera capitaneada por Alonso de Ojeda y como maestre Juan de la Cosa, y la segunda con Fernando Ladrón de Guevara como capitán y a Juan López de Sevilla como piloto. Su tripulación estaba formada en su mayoría por pescadores y marineros que ya habían participado en alguno de los viajes colombinos, por lo que ya contaban con experiencia en travesías similares.
Ojeda tuvo acceso a cartas y documentos enviados por Colón para conocer la ruta y los lugares donde se habían descubierto ríos, perlas y demás riquezas, si bien no se le permitía tocar tierras portuguesas ni las ya descubiertas por el Almirante antes de 1495, es decir, los territorios descubiertos en su tercer viaje eran perfectamente explorables.
Partieron, pues, Alonso de Ojeda y sus socios. La ruta que tomó esta expedición, luego de dejar la costa africana de Cabo Verde para cruzar el Atlántico, arribó a costas americanas un poco más al sur que Colón en su tercer viaje, cerca de la desembocadura del río Esequibo. Desde allí tomaron rumbo sur pero ante las difiultades que había de navegar optaron por volver y navegar en dirección norte pasando frente a la desembocadura del río Orinoco, llegando al golfo de Paria, las islas Trinidad y Margarita.
El 24 de agosto de 1499 descubrieron el lago de Maracaibo donde cuenta la leyenda que al adentrarse y ver varias casas indígenas situadas sobre el agua al más puro estilo veneciano decidieron llamar a ese territorio Pequeña Venecia o Venezuela.
Desde el punto de vista económico la expedición estaba resultando un absoluto fracaso ya que tan sólo pudieron recoger algunas perlas, un poquito de oro y algunos indios hostiles para ser vendidos como esclavos.
Una vez llegados a la península que Ojeda llamó Coquibacoa y teniendo a la vista el cabo de la Vela (actual Colombia) decidieron volverse a la Española arribando el 5 de septiembre al puerto de Yáquimo, unos 400 km al oeste de Santo Domingo. Una vez en la Española les interceptó Roldán que recomendó a Ojeda que se acercase a Santo Domingo para hablar con el almirante y contarle todo lo que le había narrado a él pero en vez de hacer eso tomaron rumbo oeste y continuaron adentrándose en tierra para recoger brasil y pan hecho por los indígenas (cazabe). Estas incursiones provocaron varios enfrentamientos entre los huestes de Roldán y las de Ojeda. Finalmente el capitán Ojeda regresó a Cádiz en las últimas semanas de noviembre de 1499, sin estar muy claro qué ruta tomaron, si norte hacia Cuba y luego por las Lucayas cogiendo la corriente del Golfo de México, o ruta este hacia San Juan para posteriormente tomar dirección norte hacia España.
Este sería el primer viaje de los llamados “viajes andaluces” en los que se daría un nuevo impulso al descubrimiento, colonización y conquista del nuevo continente, consiguiendo descubrir y reconocer en tan sólo 4 años casi toda la costa centro y sudamericana. Estos viajes serían ejecutados en distintas 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.