Corrió las costas de Venezuela en busca de perlas, y acabó por establecerse en lo que después fue América Central, y que los conquistadores llamaban entonces «Castilla del Oro». Una india le acompañaba como amante, guía e intérprete. Los aventureros jóvenes encontraban casi siempre entre las mancebas cobrizas ofrecidas por los azares de su existencia alguna que se apoderaba de su corazón y vivía compartiendo sus peligros. El hidalgo cristiano, al unirse con ella, había creído necesario purificarla con el bautismo—el mejor regalo, según las ideas de la época—, dándola el nombre de Isabel, en recuerdo de la buena reina.
La vida de Ojeda en la gobernación de Urabá, sin otros recursos que los que él podía agenciarse, lejos de sus compatriotas establecidos en Santo Domingo, y olvidado de España, fue un continuo batallar. Su ciudad de San Sebastián, mísera ranchería de paja y barro con un fuerte de maderos, era la primera que con carácter permanente fundaban los conquistadores en la tierra firme.
Tribus de hábiles arqueros la sitiaban a todas horas, lanzando flechas empapadas en incurables venenos. Eran las temidas «flechas de hierba», que hinchaban el cuerpo del herido con negruzca y mortal tumefacción. Los víveres del país—el pan de cazabe, los frutos de la selva, la carne de los roedores—había de conquistarlos diariamente a punta de espada. Los combates y las enfermedades diezmaban a los habitantes.
Juan de la Cosa, el sabio piloto autor del primer mapa de las Indias, había muerto atado a un poste por los naturales, erizado de «flechas de hierba», que convirtieron su cuerpo a las pocas horas en una masa de negra putrefacción. En los míseros bohíos del pueblo gemían los conquistadores mal heridos, hambrientos, temblando de calentura. Ojeda, al frente de unos cuantos, salía diariamente a combatir por la comida.
Encuentro hubo del que surgió llevando en su rodela, según los cronistas, las señales de más de trescientos flechazos. Otras veces era tanto el peso de los enemigos arremolinados sobre él, que se doblaba y seguía combatiendo de rodillas, cubriéndose con el escudo. La pequeñez de su cuerpo ágil y escurridizo le servía tanto como la fuerza de sus brazos, y de todas las peleas salía incólume, «sin que le sacasen sangre». Los indígenas creíanle poseedor de maravillosos amuletos. Ojeda también se consideraba protegido por el cielo gracias a un cuadrito antiguo de la Virgen, regalo de Fonseca, que llevaba pendiente del cinturón de la espada.
Cuatro indios arqueros se apostaron para herir a traición al capitán blanco que salía indemne de los combates, y un día que Ojeda avanzaba por la selva, extrañando la ausencia de enemigos, recibió un flechazo en un muslo. Por primera vez su cuerpo manaba sangre. La herida, que era «de hierba», ennegrecióse rápidamente por la acción del tósigo. Entonces se mostró con bárbara grandeza el coraje de aquel hombre. Hizo que calentasen en una hoguera el peto y el espaldar de una coraza, y cuando las dos planchas de acero estuvieron al rojo blanco, ordenó que se las aplicasen al mismo herido con unas tenazas. Negábase el cirujano a esta horrible curación, pero él le amenazó con la horca para que obedeciese. Chirriaron las carnes bajo el bárbaro cauterio, esparciendo un hedor de sacrificio humano. Para no desmayarse, hizo Ojeda que le envolviesen con sábanas empapadas en vinagre. Una pipa entera se consumió en este remedio; y el caudillo, gracias al espeluznante tormento, sufrido sin una queja, pudo salvarse.
La pequeña ciudad, falta de subsistencias, estaba próxima a perecer. En esto se presentaron inesperadamente unos piratas españoles, mandados por un tal Bernardino Talavera, audaz facineroso. Montaban en un buque que habían robado a un mercader genovés y se ofrecían para vender víveres a los sitiados. Ojeda, convaleciente de su herida, se embarcó con ellos para solicitar auxilios del gobernador de Santo Domingo. Pero antes de abandonar a su mísera gente quiso darla un capitán, y fijó su elección en un mozo extremeño llegado poco antes a las Indias, en el éxodo de gente de espada que siguió al de los navegantes: éxodo que llamaba Fernando «la segunda hornada de conquistadores». Este soldado, que había hecho el aprendizaje de la guerra indiana al lado de Ojeda, llamábase Francisco Pizarro.
La accidentada navegación con los piratas fue la última y más penosa aventura de don Alonso. Autoritario y duro, quiso tomar el mando apenas se vio sobre la cubierta del buque, imponiendo su disciplina a Talavera y sus bandidos. Pero éstos se sublevaron contra él y lo metieron en la cala cargado de cadenas. A pesar de esto, el prisionero no cesó en su brava actitud, asegurando que había de ahorcarlos a todos apenas llegasen a tierra. Y tanto era su prestigio, que no se atrevieron a hacer nada contra él. Muchas veces le pedían consejo, por la experiencia que había adquirido en las cosas de la navegación, y le sacaban de su encierro para que dirigiese la nave. Acabaron por abandonar ésta en las costas de Cuba, y marcharon después meses y meses por la isla todavía inexplorada, deseosos de aproximarse a Santo Domingo, pero sin saber ciertamente adónde iban, sumiéndose en ciénagas, combatiendo a los indígenas o transigiendo con ellos, atormentados por el hambre, que mataba a muchos. En esta marcha desesperada, el cautivo Ojeda se veía elevado por sus guardianes al rango de jefe cada vez que había que combatir a un grupo indígena, tratar con un cacique benévolo u orientarse en el desierto de barrizales temblorosos que se tragaban a los hombres. Él solo valía tanto como los otros. Luego, pasado el peligro, don Alonso volvía a ser prisionero de estos desalmados, que lo aborrecían por ser superior a ellos, y así marchaban juntos, condenados a tolerarse por la comunidad del infortunio. «Nunca—dice un cronista—se vio a gente pasar tantos trabajos para venir a parar en la horca.»
Cuando después de grandes tribulaciones por mar y por tierra llegaron a países sometidos a las autoridades castellanas, Talavera y sus hombres fueron ahorcados y don Alonso se vio envuelto en procesos que amargaron sus últimos tiempos. La gobernación de Urabá, que le había dado el rey, ya no existía. La mayor parte de sus soldados habían dejado en ella los huesos: otros habían perecido en el mar; sólo Pizarro y unos cuantos predestinados como él consiguieron volver a Santo Domingo.
El antiguo paje de doña Isabel arrastró en la ciudad colonial la mísera existencia de los conquistadores sin éxito. Fue un veterano malhumorado y pronto a reñir entre la bohemia juvenil de capa y espada que llegaba de la Península soñando con la conquista de tesoros y reinos. Se organizaban nuevas expediciones. Pizarro poníase a sueldo de diversos capitanes. Por las calles de Santo Domingo paseaba su garbo otro extremeño, enamoradizo, espadachín y algo letrado, que se apellidaba Cortés.