Известно, что в юности будущий открыватель морского пути в Индию участвовал в осаде марокканского города Танжера. Есть предположение, что он совершил несколько морских экспедиций вдоль африканских берегов. Может быть, именно это заставило королевский двор обратить на него внимание. Возможно, были другие причины. Как бы то ни было, Васко оказался на службе у Жуана II и сумел быстро выдвинуться.
Хроники свидетельствуют, что еще в молодости юноша отличался твердым, решительным характером, изрядной долей вспыльчивости и властными повадками. Рассказывают, что однажды ночью охрана задержала его на улицах Сетубала. Лицо молодого человека прикрывал капюшон, и стражам порядка это показалось подозрительным. Они потребовали показать лицо. Гама отказался. Тогда стражники вызвали алькайди. Прибывшему чиновнику Васко заявил: «Я не преступник», а потом двинулся прочь, не обращая внимания на вооруженных стражников и их начальника. Как ни странно, те не посмели арестовать его.
В 1497 г. новый португальский король Мануэль I Счастливый решил продолжить дело предков и отправить экспедицию на поиски морского пути в Индию. Трудно сказать, почему королевский выбор пал на двадцативосьмилетнего провинциального фидальгу Гама. Ведь особых заслуг к тому времени за ним не числилось. Видно, так уж повелось при дворе португальских королей, что руководство морскими экспедициями, часто в обход капитанов, уже успешно руководивших экспедициями в дальние страны, доверяли людям, не имевшим достаточного опыта. Однако можно с уверенностью утверждать, что Гама сумел-таки завоевать доверие короля. Иначе ему не поручили бы руководство экспедицией, на которую Мануэль возлагал очень большие надежды.
Хронисты того времени по-разному описывают то, каким образом будущий граф Видигейры получил назначение. Некоторые утверждают, что главой экспедиции вначале был назначен отец Гамы, но после его смерти поручение перешло к среднему сыну. Другие пишут, что ему пришлось заменить старшего брата Паулу, который отказался от командования, сославшись на слабое здоровье. Более привлекательной для большинства хронистов является версия о том, что король сразу остановил свой выбор на Васко, предложив ему взять одного из братьев в качестве капитана какого-нибудь из кораблей. Монарх будто бы остался очень доволен скромным поведением своего избранника, который пытался отказаться от командования в пользу брата, но в конце концов согласился. Довольный король якобы сказал: «Мое сердце говорит мне, что вы исполните мое поручение, поэтому распоряжайтесь всем по своему усмотрению, вам одному я даю все полномочия».
Молодой командующий занялся подготовкой к экспедиции. Он вникал в состояние кораблей, качество оснастки, погрузку запасов. Самолично набирал Гама и команду. Капитаном одного из кораблей в соответствии с советом короля он выбрал своего любимого брата Паулу. Возможно, таким образом он спасал его от серьезных неприятностей. Паулу умудрился в ссоре серьезно ранить судью города Сетубал и скрывался от закона. Король простил его, но дал понять, что делает это только в расчете на верную службу со стороны Васко.
Вечером 7 июля 1497 г. Васко да Гама вместе с братом Паулу и офицерами прибыл в церковь Св. Марии Вифлеемской в пригороде Лиссабона, построенную еще Генрихом Мореплавателем. Здесь они исповедовались в грехах и причастились. Утром, вскоре после рассвета, перед церковью стала собираться толпа. Родственники мореплавателей, матросы, солдаты, женщины в черных платках оплакивали смельчаков, отправляющихся в дальнее и опасное плавание. По словам хрониста Барруша, плачущих во время отплытия было так много, что берег перед церковью можно было назвать «Берегом слез». Васко да Гама был тронут таким проявлением сочувствия и даже прослезился, но взял себя в руки и повел команду на прощальную мессу. После богослужения все направились к берегу, где их ждали лодки, чтобы отвезти на корабли. Впереди шли священники. За ними в полном одиночестве, с высоко поднятой головой и сурово сжатыми губами шествовал Гама, держа в руке зажженную свечу. Вслед за командором, по два в ряд, шли, тоже со свечами, офицеры и матросы. На берегу все упали на колени. Прелат принял общую исповедь и даровал полное прощение грехов всем, кто сложит голову в путешествии. Команда погрузилась в лодки и отправилась на корабли. Над мачтой флагманского судна «Сан-Габриэль» взвился королевский флаг, застучали барабаны, заиграли волынки и бубны, тамбурины и флейты. Историческая экспедиция началась.