Корабль вез колонистов и припасы в Новую Андалусию. Возле устья Магдалены Энсисо встретил судно Франсиско Писарро с 25-30 людьми на борту. Но до карибского берега добрался только один корабль, второй же, с припасами, потерпел крушение. Колонистам с самого начала угрожал голод. Тогда по предложению де Бальбоа они переправились на Панамский перешеек, формально являвшийся частью "Золотой Кастилии"" Нерваэса. Сразу же конкистадоры разграбили покинутое индейское селение, где нашли съестные припасы, ткани и золото. После этой удачи на Бальбоа стали смотреть как на предводителя, его избрали судьей, а Энсисо лишили полномочий на том основании, что его права не распространялись на "Золотую Кастилию".
Встав во главе колонии "Золотая Кастилия", Бальбоа посадил основателя испанского поселения на Панамском перешейке Никуэса с несколькими верными ему людьми на ветхое судно и без всяких припасов пустил в океанское плавание. Никуэс пропал без вести.
В распоряжении Бальбоа к 1511 году было только 300 матросов и солдат, из которых не больше половины могло еще держаться на ногах. С такими небольшими силами он начал завоевание внутренних областей "Золотой Кастилии". Бальбоа понимал, что его сил недостаточно для покорения страны. Поэтому он воспользовался враждой между местными племенами и заключал союзы с одними, чтобы побеждать других. Союзники снабжали испанцев припасами или отводили им земли и сами их обрабатывали. Вражеские селения конкистадоры разоряли, а пленных продавали. Вождь одного из племен, изумленный жадностью, с какой европейцы набрасывались на золото, сообщил, что в нескольких днях пути к югу от Дарьенского залива лежит густонаселенная страна, где много золота, но для ее покорения нужны большие силы. Вождь прибавил, что там с горных вершин можно видеть другое море, по которому ходят суда, по размерам не уступающие испанским кораблям.
На поход к этому "Южному морю" Бальбоа решился только через два года, когда из Эспаньолы пришла весть, что правительство рассматривает его обращение с наместником Никуэсом как мятеж против королевской власти. Бальбоа понимал, что только великий подвиг может спасти его,
В 1513 году он двинулся на судах от устья Атрато на северо-запад, вдоль Атлантического побережья, и, пройдя около 150 километров, высадился на берег. Чтобы устрашить индейцев, Бальбоа лицемерно обвинил в мужеложестве мужчин, которые прикрывали наготу короткими кусками ткани, напоминающими женские передники. "Преступники" были затравлены собаками, сопровождавшими конкистадоров в походах.
Бальбоа сумел нагнать на индейцев-карибов страх не только собственной жестокостью, но и кровожадностью своего свирепого пса Леончилло, который
1 сентября Бальбоа отправился открывать "Южное море" с отрядом из ста восьмидесяти наиболее смелых и выносливых солдат. Экспедицию сопровождали шестьсот индейцев-носильщиков и свора борзых.
Панамский перешеек, который нужно было пересечь, чтобы добраться до берега неизвестного моря, имеет не более шестидесяти миль в ширину, но зато он перерезан на всем протяжении цепями высоких гор, у подножия которых образовалась наносная, необыкновенно плодородная почва, поросшая буйной тропической растительностью. Испанцам пришлось прорубаться через непроходимые чащи лиан, папоротников, гигантских деревьев, преодолевать вязкие болота с тучами москитов. Этот лес был населен множеством птиц и животных, чей покой доселе человеком не нарушался. Ядовитые испарения болот, желтая лихорадка и дизентерия, свирепствовавшие в этих местах, изматывали силы и убивали энергию самых здоровых людей.
Завидев грозный отряд Бальбоа, туземцы убегали в горы или, пользуясь преимуществами хорошо защищенной местности, совершали на испанцев неожиданные нападения. Бальбоа старался поддерживать в своих людях бодрость духа и заставлял их двигаться вперед.