В Венесуэле Федерман не стал сидеть сложа руки. Он разорил несколько индейских селений, набрал две сотни рабов-носильщиков и со ста десятью пехотинцами и двумя десятками всадников устремился на юг, к Южному морю, берега которого, как он полагал, завалены жемчугом и золотыми слитками. В долине реки Баркисимето Федерман обнаружил несколько крупных селений — тамошние жители подарили ему золотые безделушки и подтвердили сведения о море, лежащем к югу. И такие подтверждения Федерман получал на протяжении всего своего пути. Индейцы вовсе не намеренно морочили конкистадорам голову: дело в том, что толмачи передавали понятие «море» словом «парагуа» (букв.: «большая вода»), а индейцы понимали под этим словом не только море, но также широкую реку или крупное озеро.
Следуя указаниям туземцев, конкистадоры пересекли горный кряж — и перед ними распахнулось море. Бескрайнее море венесуэльских равнин — льянос. На равнинах с их влажным и жарким климатом многие христиане заболели лихорадкой. Больных несли в гамаках и везли на лошадях, а чтобы у туземцев, встречавшихся по пути, не возникло сомнений в бессмертии христиан, конкистадоры представляли заболевших большими начальниками. «Войско продвигалось медленно, словно цыганский табор или толпа инвалидов», — вспоминал впоследствии Федерман. Носильщики — кто повымерли, кто разбежались, и тогда конкистадорам пришлось оставить часть провизии и снаряжения, взяв с собой лишь самое необходимое. Пошли безлюдные места, и начался голод. Люди роптали и требовали повернуть назад. «Если бы так продолжалось еще какое-то время, — признавался Федерман, — жизни моей угрожала бы немалая опасность со стороны моих сотоварищей». Ситуация изменилась, когда конкистадоры достигли населенных районов и принялись грабить деревни, попадавшиеся по пути. Если туземцы оказывали сопротивление, их безжалостно убивали, после чего Федерман объяснял покорившимся вождям, что сам-то он пришел с мирными намерениями, но поведение индейцев вызвало гнев «божеств» (коней), а он лишь подчиняется их священной воле.
В декабре отряд вышел к крупному селению Акаригуа, где вместе с прилегающими деревнями проживало около пятнадцати тысяч индейцев. Туземцы на удивление мирно приняли непрошеных гостей. Чтобы закрепить мир не только словом, но и делом, конкистадоры на всякий случай взяли заложником вождя, а потом, как и обещали жителям Акаригуа, устроили карательную экспедицию против враждебного им племени. В ходе той экспедиции Федерман спалил несколько селений, пролил море крови и захватил в плен шестьсот человек — из них двести раненых он отдал индейцам, а четыреста здоровых распределил среди своих людей.
Окрепнув, конкистадоры двинулись дальше на юг. В селении Техибера они получили сведения о том, что через три дня пути достигнут холма, откуда видно море. В нетерпении Федерман оставил свое медлительное войско и с сорока всадниками устремился вперед. Когда он взошел на холм, то в туманной дали действительно увидел множество селений и «большую воду», но так и не смог понять, что это было — море, озеро или широкая река. Скорее всего, он наблюдал один из крупных притоков Ориноко.
Федерман вернулся к основному войску, намереваясь двинуться к побережью «моря». Но путь конкистадорам перерезало десятитысячное войско индейцев. В кровавой битве христиане одержали победу, подстрелив из аркебузы вождя, но почти все получили ранения, в том числе и сам Федерман. Тогда он решил возвратиться в Коро за подкреплением. На пути в Акаригуа конкистадоров поджидала засада, о которой они узнали заранее. Пока Федерман для отвода глаз вел переговоры с вождем, конкистадоры окружили индейское войско и по сигналу бросились в атаку. «Мы убили многих, а прочих обратили в бегство, — вспоминал Федерман. — Всадники ударили в самую гущу туземцев, сшибая наземь всех подряд, а пехотинцы перерезали им горло, как свиньям. Некоторые попытались схорониться в густой траве или спрятаться под кучами мертвых тел, но, расправившись с убегавшими, мы их нашли и удавили». Обратный путь оказался нелегким: заслышав о приближении христиан, индейцы покидали селения и забирали все, что могли унести. В горах к мукам голода добавились муки жажды. В марте 1531 г. поредевшее войско Федермана вернулось в Коро.