Отставной моряк Родриго Бастидас, на короткое время ставший купцом, выхлопотал разрешение снарядить два корабля. В качестве штурмана и компаньона он пригласил Хуана Ла Косу. Они отплыли из Испании в октябре 1500 г. и на пути к Южной Америке усмотрели остров, благодаря пышной растительности названный Исла Верде (о. Зеленый), вероятно о. Барбадос.
Бастидас достиг мыса Ла-Вела, прошел к юго-западу вдоль низменного побережья и в начале мая 1501 г. увидел величественный горный массив, покрытый вечным снегом (Сьерра-Невада-де-Санта-Марта, вершина — 5780 м). На склонах гор и на равнине жили таиронас, индейцы одного из наиболее цивилизованных племен к востоку от Анд. Испанцы наладили с ними торговые контакты и, так как те были дружелюбно настроены, оставили у них Хуана Буэнавентуру.
Он прожил среди индейцев чуть больше года, научился языку, познакомился с их образом жизни, а в мае 1502 г. присоединился ко второй экспедиции Охеды.
Западнее массива Сьерра-Невада Бастидас открыл устья многоводной р. Магдалены и р. Сину, впадающей в залив Картахена (Морроскильо). У 76° з. д. испанцы обнаружили несколько мелких островов, до сих пор носящих присвоенное им название Сан-Бернардо, и впервые проникли в Дарьенский залив и его южную узкую часть — залив Ураба. От индейцев Бастидас узнал, что в долине р. Аррато есть золотые рудники, до которых можно подняться на каноэ или небольших лодках, но не стал рисковать: к этому времени он награбил и выменял 30 кг золота и массу жемчуга, захватил на берегах Магдалены много рабов-карибов, имел на борту большой груз бразильского дерева. В заливе Ураба флотилия простояла несколько дней. Испанцы выменивали золото, высаживались, по словам Васко Нуньеса Балъбоа, участника плавания Бастидаса, «на западной стороне залива и видели значительную деревню на обоих берегах большой реки...». Затем экспедиция проследовала на северо-запад вдоль гористого побережья Панамского перешейка до небольшого залива у 77°30' з. д., закончив открытие Карибского побережья на протяжении около 1000 км. Отсюда Бастидас вынужден был повернуть назад: воды Дарьена кишели моллюсками-древоточцами, разрушавшими корпуса судов. В начале 1502 г. он бросил у берегов Эспаньолы свои корабли, пришедшие в полную негодность. Правитель острова Ф. Бовадилья арестовал и пытал его, обвиняя в незаконном торге, и отправил на суд в Кастилию (сентябрь 1502 г.). Но Бастидас изобразил индейцев-карибов с р. Магдалены такими кровожадными людоедами, что его оправдали и он получил даже большую пенсию в награду за открытия. А «каннибалов» королевским указом 1503 г. разрешено было убивать и уводить в неволю.