Однако так хорошо начинавшееся дело очень скоро стало разваливаться от серьезных разногласий среди колонистов, что привело к изгнанию самого Энсисо и его возвращению в Испанию, где он впоследствии напишет хорошую книгу по географии, но до этого снова вернется в Дариен, где сыграет роковую роль в судьбе Бальбоа Руководство колонией по желанию самих поселенцев выпало теперь на популярного среди всех и очень обходительного Бальбоа. Из трех партнеров, начинавших создание первого поселения в заливе Дариен-Ураба, теперь остался один Никуэса, который не преминул через некоторое время появиться в Санта-Марии. Но его грубое поведение и надменное обращение восстановило против него колонистов, по требованию которых Бальбоа выслал его из поселения, предоставив ему старую бригантину, впоследствии погибшую у побережья Центральной Америки со всем экипажем. Сын Колумба Диего, ставший к этому времени губернатором Санто-Доминго и вторым Адмиралом, уполномочил Бальбоа временно выполнять обязанности губернатора Санта-Марии-де-ла-Антигуа. В соответствии с этим решением Бальбоа направил в Испанию каравеллу с поручением капитану передать его просьбу королю Фердинанду подтвердить решение Диего Колумба. Вернувшееся из Испании судно вместо запрошенного подтверждения привезло Бальбоа совет сделать на своем временном посту что-то действительно важное или ожидать вызова ко двору с отчетом за свое поведение и дела. За таким ответом уже стояли неблаговидные действия обиженного Энсисо, который не останавливался ни перед чем, чтобы оклеветать и убрать с его поста благородного и честного Бальбоа.
За короткое время на посту главы колонии Санта-Мария Васко Бальбоа не только завоевал доверие и уважение поселенцев за свой дружелюбный характер и справедливый подход к людям, но и смог в отличие от многих других конкистадоров наладить необычно добрые отношения с местным населением, прекрасно понимая, насколько важно это было для успеха дела. Он стал, среди прочего, кровным братом вождя крупного местного племени Карета, с которым сначала встретился в бою, но затем завоевал его доверие и расположение и даже взял по его предложению в качестве неофициальной жены одну из красивых дочерей этого касике по имени Анаянси. Именно это племя обеспечивало испанцев продовольствием, а они помогали индейцам в их борьбе с местными врагами. После одной из таких войн касике Комогре и его сын Пакиано передали Бальбоа большое количество золотых украшений, которые весили свыше 130 килограмм. При этом касике сообщил испанскому идальго о том, что на западе в 3—4-х неделях пешего пути находится огромное море, а в южной его стороне существует очень богатая страна, где золота так много, что им покрывают стены больших каменных домов. Бальбоа принял к сведенью это потрясающее сообщение и стал готовиться к далекому походу к Южному морю.
В конце августа 1513 года эти приготовления были завершены, а 1 сентября Бальбоа со 190 испанцами и 810 индейцами вышел из Санта-Марии-дель-Дариен при одной бригантине и 10 каноэ в Акла, находившейся в земле касике Карета, который к этому времени уже принял христианство под именем Дон Фернандо. Хотя перешеек в том месте имеет всего около 140 миль в ширину, а горы не поднимаются выше 300 метров, его пересечение даже до недавнего времени оставалось невероятно тяжелым делом. Трудности этого пути связаны с необыкновенно густыми тропическими зарослями, продвижение через которые можно совершать только постоянным прорубанием кустов, деревьев, лиан и другой растительности. Но еще большие проблемы вызваны необходимостью преодолевать бесконечное число болот и озер в условиях чудовищной жары и удушающей влажности, не говоря уже об обилии насекомых, змей и разных животных, которые вызывали страхи и ужасы у европейцев. Такие водные препятствия можно было преодолевать только вплавь или переходом через броды, неся на головах и руках тяжелые доспехи, оружие, снаряжение и пропитание. Немало хлопот доставляли также и схватки с некоторыми индейскими племенами. Таким образом Бальбоа продвигался со своим отрядом от деревни к деревне, пользуясь поддержкой тех местных касике, с которыми ему удавалось налаживать хорошие отношения и у которых ему приходилось оставлять растущее число больных людей.