Né vers 1460 à Séville, notaire avec une position sociale élevée, il obtint de la Couronne, le 5 juin 1500 une capitulation pour un voyage d'exploration de territoires des Indes, non découverts par Christophe Colomb.
Il partit de Cadix en octobre 1500 avec deux bateaux, accompagné de Juan de La Cosa qui avait accompagné Colomb lors de son premier voyage, comme propriétaire de la caravelle Santa Maria. Juan de La Cosa avait également participé à la première expédition d'Alonso de Ojeda. Accompagnait également Bastidas, Vasco Nuñez de Balboa, le futur découvreur de la Mer du Sud. Dans cette expédition, ils longèrent toute la côte nod du continent sud-américain, la Tierra Firme, depuis le Vénézuela jusqu'au Panama actuel, découvrant au passage les sites des futures villes de Santa Marta, Cartagène, le Golde d'Urabá et les côtes du Panama où plus tard seront implantées les villes de Nombre de Dios et de Puerto Bello. Ce n'est que l'année d'après que Colomb explorera cette côte lors de son quatrième voyage, en longeant du nord au sud, les côtes du Honduras et du Panama acuels. Bastidas mit fin à cette expédition en raison du mauvais état des bateaux rongés par les tarets. Il décida de rentrer à Hispaniola.
Il arriva à Santo Domingo, pour être dépouillé du butin accumulé pendant l'expédition, et jeté en prison par le gouverneur Francisco de Bobadilla, sous le prétexte que ses commissions royales qui l'autorisaient à commercer avec les indigènes sur les terres découvertes, ne l'autorisaient pas à le faire sur l'île d'Hispaniola, qu'il avait du traverser à pied, ses bateaux ayant coulé en touchant la côte. Il dut rentrer en Espagne pour être jugé.
A cette époque, Bobadilla fut remplacé par un nouveau gouverneur, Nicolas de Ovando, et la flotte l'ayant amené, faisait le trajet de retour, avec à son bord, Bobadilla, Francisco Roldán, deux ennemis de Christophe Colomb. Ce dernier, était arrivé dans l'île le 29 juin 1502, lors de son quatrième voyage. La flotte de Bobadilla partit le 30 juin, contre l'avis de Colomb, qui les mit en garde contre l'imminence d'un ouragan. On ne tint pas compte de son avertissement ; plus de 20 bateaux coulèrent dans la tempête, Bobadilla et Roldán perdirent la vie. Le bateau de Bastidas échappa au naufrage.
Bastidas fut jugé et acquitté en 1503 en Espagne. Il revint rapidement à Santo Domingo où il s'établit comme encomiendero et éleva jusqu'à 8000 têtes de bétail.
En 1520-21, il obtint de l'Empereur le titre d'adelantado des territoires compris entre le Cap de La Vela et le Rio Magdalena (actuelle ville de Baranquilla en Colombie). Il partit en 1524 de Santo Domingo, avec 5 caravelles et 450 colons (dont un tiers de femmes). Il fonda la ville de Santa Marta. Il entretint avec les indigènes des relations amicales faites de respect mutuel, ayant fondé pour eux le village de Tarbo, non loin de Santa Marta, avec interdiction faite aux Espagnols d'y prendre quoi que ce soit.
Commerçant riche et prospère, il avait équipé à ses frais, trois bateaux de l'expédtition de Cortés au Mexique.
Cette politique n'était pas approuvée par tous, puisque deux de ses lieutenants, Pedro de Villafuerte et Pedro de Porras organisèrent son assassinat. En 1527, ils le blessèrent gravement de plusieurs coups de poignard. Rodrigo de Bastidas voulut se faire soigner à Santo Domingo, mais son état empira pendant le voyage. Des vents contraires obligèrent le bateau qui le conduisait, à faire escale à Santiago de Cuba, où il mourut.
Ses assassins furent jugés à Santo Domingo, et condamnés à mort. La sentence fut exécutée malgré l'aministie générale prononcée par Charles Quint, à l'occasion de la naissance de son fils (le futur Philippe II), amnistie dont refusèrent de tenir compte les représentants de l'Audiencia de Santo Domingo. Les autres conspirateurs furent grâciés.
