Получив по распоряжению Изабеллы и Фердинанда флотилию из четырех каравелл, в январе 1502 года Охеда снова отправился за океан. К этому времени Испания, внимательно следившая за морскими экспедициями своих новых соперников Англии, Франции и Нидерландов, была обеспокоена их возможными посягательствами на свои новые земли, и в этой связи лихой Охеда получил также поручение выдворить проникших туда самозванцев. Однако эту задачу губернатору Кокивакоа решать не пришлось, так как эти соперники Испании в те края еще не добрались. Но проявить свой неизменный пиратский нрав ему все-таки удалось. Прекрасно зная, что дорога на Канарские острова ему теперь была закрыта, для пополнения запасов перед переходом через океан Охеда сделал остановку на островах Зеленого Мыса Здесь он не преминул устроить скандал с португальскими властями, которые в результате арестовали главного судовладельца испанской флотилии. В отместку за это Охеда захватил двух местных жителей в плен и вынужденно покинул порт, не получив необходимых запасов.

Ему повезло, что погода помогла его экспедиции пересечь Атлантику довольно быстро, поскольку по прибытии в залив Пария к началу второй декады марта экипажи уже начинали страдать от голода. Действуя в своем обычном духе, Охеда содержал людей за счет разорения местного населения этих земель и одновременно собирал жемчуг и другие ценности. Через две недели его флотилия находилась уже на подступах к Маргарите, когда разбилась и затонула одна из каравелл. Здесь снова обострилось положение с продовольствием, и Охеда решает послать за ним один из парусников на довольно близкую Ямайку. Месяц спустя судно оттуда так и не вернулось. Дело с пропитанием становилось все острее, что вынуждает капитана флотилии направить туда еще одну каравеллу, а с двумя оставшимися парусниками он отправляется вдоль континента на запад, по какой-то причине не оставив даже, как планировалось, торговую факторию на Жемчужном берегу.

Пройдя залив Маракайбо, Охеда плывет до полуострова Гуахира, на дальнем берегу которого он находит залив, названный им бухта Глубокая, где он решает основать колонию Кокивакоа в качестве столицы своей губернии. Место это оказалось крайне неудачным: там не было ни жемчуга, ни золота, а местные враждебно настроенные индейцы и комары не оставляли испанцев в покое. Голодающие экипажи не выдержали таких трудных условий и жесткой власти губернатора, подняли мятеж, заковали его в цепи и отправились искать спасения в Санто-Доминго. Там местные власти припомнили Охеде его прежние бунтовские выходки на Эспаньоле и, конфисковав всю принадлежавшую ему на острове собственность, бросили губернатора Кокивакоа в тюрьму. В заключении он пробыл несколько месяцев, до тех пор, пока его могущественному опекуну Фонсеке не удалось вызволить своего подопечного на свободу в Испанию. Два года спустя непотопляемый Охеда подписывает с короной новое соглашение об основании поселения на континенте в районе залива Ураба, но с условием, что он не будет посягать на территорию Колумба и что вся его торговля будет проходить через контроль в Санто-Доминго. Однако эта экспедиция так и не состоялась, вероятно, из-за отсутствия необходимых средств...

С того времени прошло четыре года, когда неукротимый Охеда вдруг снова появился на арене экспедиций в Новый Свет. В 1508 году новая королева Кастилии Хуана назначает его и другого лихого идальго Диего де Никуэса, находившегося тогда на службе у губернатора Овандо на Эспаньоле, совместными правителями протяженной береговой полосы нового континента от залива Маракайбо до Дариена на Панамском перешейке. В этой связи оба идальго встретились в Санто-Доминго и страшно не понравились друг другу, возможно, по причине удивительного сходства их характеров. Сразу поняв, что их совместное губернаторство на выделенной им территории является просто немыслимым, они решили поделить ее между собой на независимые восточную и западную части, первая из которых оказалась у Охеды. Им удалось также договориться взять в партнеры работавшего на Эспаньоле адвокатом Мартина Энсисо, который в дополнение к финансовому участию в общем деле должен был заняться в Санто-Доминго набором будущих колонистов, а самим направиться каждому в свою собственную вотчину для подготовки мест поселения.

На этот раз Охеда смог выбрать одну из лучших гаваней карибского побережья, которую он назвал Картахена-де-лас Индиас и где решил основать новую колонию, ставшую впоследствии великолепной морской крепостью, а затем и вторым самым крупным городом Колумбии. Прибывшие вскоре туда примерно 300 колонистов сразу же начали совершать рейды по окружающим индейским поселениям для захвата рабов, жемчуга и золота Восставшие против этих бесчинств индейцы стали нападать на испанцев, применяя ядовитые стрелы, что привело к гибели 69 поселенцев и получению ранения самим Охеда. Последний спас себе жизнь от неминуемой смерти, приказав одному из своих солдат прижечь раскаленным мечом рану на ноге.

Столкнувшись с ожесточенным сопротивлением индейцев, Охеда был вынужден покинуть облюбованную им великолепную базу и перенести колонию на восточный берег залива Ураба, назвав новое место Сан-Себастьян. Однако через некоторое время поселенцы и здесь прибегли к тем же бесчинствам по отношению к местному населению и получили такой же отпор, что и в Картахене. На сей раз индейцы загнали испанцев в укрепленный форт и окружили его. Положение колонистов складывалось настолько серьезным, что Охеда был вынужден направить свою единственную каравеллу за помощью на Эспаньолу. Но помощь почему-то задерживалась, и тогда Охеда решает отправиться за ней сам на случайно оказавшемся у Сан-Себастьяна пиратском судне. Вместо себя он оставляет во главе форта смелого и опытного Франсиско Писарро, который через два десятка лет прославит свое имя невероятным завоеванием империи инков.

Пиратский парусник с Охеда сначала направился к берегам Кубы, где к его большому невезенью сел на мель. Отсюда неукротимый капитан все-таки сподобился добраться до Санто-Доминго, где его партнер Энсисо сообщил ему, что он уже отправил одну каравеллу для вывоза осажденных колонистов из Сан-Себастьяна. Однако это сообщение оказалось единственной положительной новостью для Охеды, поскольку он вскоре был арестован и отдан под суд в связи с очередным обвинением в преступлениях, совершенных им в его провинции и в других местах. Судебное преследование не только привело этого столь везучего конкистадора к тюремному заключению, но и полному разорению. Алонсо Охеда умер в Санто-Доминго в 1515 году в ужасной нищете. В отличие от многих других пионеров Нового Света Охеда не был ни выдающимся мореплавателем, ни картографом, ни старательным исследователем. Его скорее можно охарактеризовать как авантюриста и конкистадора, искавшего богатства, славы и приключений, который благодаря высокой поддержке, а также собственной смелости и дерзости смог внести свою скромную лепту в открытие части северо-западного и северного побережья Южной Америки вместе с несколькими небольшими островами и в их освоение.

В последней авантюре Охеды принимал участие и уже знакомый нам Хуан де Ла Коса, который сопровождал Колумба в его первых двух плаваниях, а затем оказался вместе с Америго Веспуччи и в первой самостоятельной экспедиции лихого авантюриста. Де Ла Коса был одним из самых талантливых мореплавателей и картографов своего времени — качества, которые он особенно ярко проявил во время экспедиций в Индии. Самая первая географическая карта открытой на то время части Карибского моря и его островов была опубликована в 1500 году и носит название карты де Ла Коса Его замечательные достоинства были высоко ценимы испанскими монархами, которые в начале 1504 года предоставили ему лицензию на осуществление самостоятельной экспедиции в залив Ураба и в другие территории Нового Света. К этому времени Ла Коса приобрел не только большой опыт походов в Индии, но и немалое богатство, что позволило ему организовать эту экспедицию за собственный счет лишь при незначительной финансовой поддержке еще одного партнера.