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