В распоряжении Бальбоа к 1511 году было только 300 матросов и солдат, из которых не больше половины могло еще держаться на ногах. С такими небольшими силами он начал завоевание внутренних областей "Золотой Кастилии". Бальбоа понимал, что его сил недостаточно для покорения страны. Поэтому он воспользовался враждой между местными племенами и заключал союзы с одними, чтобы побеждать других. Союзники снабжали испанцев припасами или отводили им земли и сами их обрабатывали. Вражеские селения конкистадоры разоряли, а пленных продавали. Вождь одного из племен, изумленный жадностью, с какой европейцы набрасывались на золото, сообщил, что в нескольких днях пути к югу от Дарьенского залива лежит густонаселенная страна, где много золота, но для ее покорения нужны большие силы. Вождь прибавил, что там с горных вершин можно видеть другое море, по которому ходят суда, по размерам не уступающие испанским кораблям.

На поход к этому "Южному морю" Бальбоа решился только через два года, когда из Эспаньолы пришла весть, что правительство рассматривает его обращение с наместником Никуэсом как мятеж против королевской власти. Бальбоа понимал, что только великий подвиг может спасти его, "скудно одаренного человека, не из дворян", от суда и виселицы.

В 1513 году он двинулся на судах от устья Атрато на северо-запад, вдоль Атлантического побережья, и, пройдя около 150 километров, высадился на берег. Чтобы устрашить индейцев, Бальбоа лицемерно обвинил в мужеложестве мужчин, которые прикрывали наготу короткими кусками ткани, напоминающими женские передники. "Преступники" были затравлены собаками, сопровождавшими конкистадоров в походах.

Бальбоа сумел нагнать на индейцев-карибов страх не только собственной жестокостью, но и кровожадностью своего свирепого пса Леончилло, который "один стоил двадцати солдат". Впрочем, Бальбоа был дальновиднее своих предшественников и без особой надобности не прибегал к расправам.

1 сентября Бальбоа отправился открывать "Южное море" с отрядом из ста восьмидесяти наиболее смелых и выносливых солдат. Экспедицию сопровождали шестьсот индейцев-носильщиков и свора борзых.

Панамский перешеек, который нужно было пересечь, чтобы добраться до берега неизвестного моря, имеет не более шестидесяти миль в ширину, но зато он перерезан на всем протяжении цепями высоких гор, у подножия которых образовалась наносная, необыкновенно плодородная почва, поросшая буйной тропической растительностью. Испанцам пришлось прорубаться через непроходимые чащи лиан, папоротников, гигантских деревьев, преодолевать вязкие болота с тучами москитов. Этот лес был населен множеством птиц и животных, чей покой доселе человеком не нарушался. Ядовитые испарения болот, желтая лихорадка и дизентерия, свирепствовавшие в этих местах, изматывали силы и убивали энергию самых здоровых людей.

Завидев грозный отряд Бальбоа, туземцы убегали в горы или, пользуясь преимуществами хорошо защищенной местности, совершали на испанцев неожиданные нападения. Бальбоа старался поддерживать в своих людях бодрость духа и заставлял их двигаться вперед.

После двадцатидневного перехода, сопровождавшегося непрерывными боями с индейцами, Бальбоа, поднявшись на гребень горы, увидел, наконец, широкий Панамский залив, за которым открывалось безбрежное "Южное море" - Тихий океан. 29 сентября он вышел к бухте, которую назвал Сан-Мигель. Дождавшись прилива, Бальбоа вошел в воду и, с обнаженной шпагой в одной руке и с кастильским знаменем в другой, торжественно прочитал грамоту, составленную нотариусом: "... вступаю во владение для кастильской короны... этими южными морями, землями, берегами, гаванями и островами со всем, что в них содержится... И если иной царь или вождь, христианин или сарацин... заявит свои притязания на эти земли и моря, то я готов во всеоружии оспаривать их у него и воевать с ним во имя государей Кастилии, как настоящих, так и будущих.