Basados en los informes de Fray Bartolomé de las Casas y Gonzalo Fernández de Oviedo quienes estuvieron muy relacionados con Rodrigo de Bastidas, se concluye que una vez iniciado el viaje, los navíos llegaron a una de las ocho islas del archipiélago canario, la Gomera, y de allí enfilaron su viaje a través del Atlántico. Esta expedición fue la primera en recorrer la costa norte de Sur América, que se llamó Tierra Firme.
Navegaron el Golfo de Venezuela, avistaron el Cabo de la Vela, Riohacha, la bahía de Santa Marta, la desembocadura del rio Grande de la Magdalena. Cartagena de Indias, la Isla de Barú, Isla Fuerte, la desembocadura del río Sinú, la bahía de Cispatá, Punta Caribana, entrando al Golfo de Urabá al que llaman Golfo Dulce, sin reconocer la influencia del río Atrato cuyo caudal dio origen al nombre de Golfo Dulce, continuando hasta el puerto de Retrete, donde quiso fundar el puerto El Escribano en su honor.
Los mares tropicales tienen unos pequeñitos moluscos conocidos como “broma” , que se adhieren a las superficies de madera literalmente comiéndosela. Rodrigo de Bastidas fue el primero en sufrir las consecuencias de estos moluscos. En Puerto Retrete cuando decide regresar a España con sus navíos, ya la “broma”había hecho su tarea y difícilmente llegan a Jamaica por el mal estado de sus navíos.
Al llegar a Jamaica recibió noticias en las cuales Francisco de Bobadilla lo acusaba de tráfico de armas y rescate de indígenas a cambio de oro, lo que no estaba autorizado. Fue encausado para ser juzgado, y después de varios intentos de regresar a España, finalmente a fines de 1.502, atracó en Cádiz, donde debió permanecer bajo jurisdicción del corregidor a fin de asistir al juicio que se le había abierto en Santa Domingo y a pagar, en caso de que resultase culpable.
Para el 3 de abril de 1.503, estaba en Alcalá de Henares, donde residían los reyes en ese momento y donde se desarrolló su juicio. Fué tan hábil su defensa que a fines de año se dictó sentencia absolutoria y se le premió con una pensión de 50.000 maravedíes al año .
Durante su estancia en Santo Domingo Bastidas observó el comercio que se estaba desarrollando y el potencial que tenía esa actividad en un mundo donde todo estaba por hacer. De manera que solicitó otra capitulación que le fue concedida, radicándose en Santo Domingo. Allí amasó una fuerte fortuna con ganado, llegando a tener 8.000 cabezas de reses y ovejas, construyó muchas casas que rentaba y comerciaba perlas. Sin embargo, ansiaba volver a navegar y a fundar ciudades; así que volvió a pedir una capitulación para fundar una ciudad en la bahía que había bautizado como Santa Marta, mas de veinte años atrás.