Выбор короля пал на Афонсу ди Албукерка, который разделял его взгляды и видел в нем мессию, что призван вытеснить мусульман из Индийского океана и вернуть Иерусалим христианам.
И вот 27 февраля 1506 года, вскоре после официального объявления Мануэла о полном доверии Алмейде, Афонсу ди Албукерк подписал секретный документ: «Я, Афонсу ди Албукерк, подтверждаю, что принес клятву лично государю хранить в секрете свое назначение на пост правителя Индии, который в данный момент занимает дом Франсишку ди Алмейда. Обязуюсь не разглашать сей факт до его возвращения в Португалию либо до случая его внезапной смерти и своего вступления в должность».
Однако должность Албукерка называлась губернатор — то есть правитель, обладающий меньшей властью, чем вице-король. Эти сведения также были государственной тайной. Алмейде король направил записку, уведомляя его, что он изымает из-под его начала некоторые регионы в западной части Индийского океана и передает их Албукерку. Возникшее таким образом двоевластие породило путаницу и антагонизм между двумя командующими на годы вперед. Тон Мануэла в переписке с Алмейдой изменился, стал более резким — очевидно, капитаны из тех, что были недовольны принципиальностью Алмейды, возвращаясь в Лиссабон с грузами, возводили на вице-короля поклепы, к радости его завистников при дворе.
Весной 1506 года в Индию отправлялся очередной флот: пятнадцать судов под командованием Триштана да Куньи и Албукерка. На небольшом острове Сокотра, удобно расположенном близ входа в Красное море, португальцы планировали задержаться и возвести форт. Остров якобы контролировали христиане, он был удобен для перехвата мусульманских кораблей, следующих на исламские рынки Египта и Ближнего Востока.
В начале столетия, благодаря наплыву сокровищ из Индии, Лиссабон переживал большой подъем. Торговцы, моряки, ремесленники, авантюристы, привлеченные ароматом специй, стремились в Лиссабон со всех концов Европы в надежде обогатиться или найти себе применение. За динамизм и бурную деловую активность Лиссабон прозвали Новая Венеция. Но были здесь не только набережные и королевский дворец, поражавшие имперским великолепием, где отразились большие амбиции короля-бакалейщика, но и сутолока, грязь и дьявольские страсти. В январе 1506 года разразилась эпидемия чумы, вероятно завезенная из-за моря. Когда люди начали умирать по сотне человек в день, король задумался об эвакуации.
В конце марта он перенес двор в Абрантеш, в сотне миль от Лиссабона. В церквях служили мессы во имя избавления от напасти, по улицам бродили кающиеся грешники в монашеских клобуках. Людей для нового похода в Индию впервые не хватало — многие опасались заболеть, оказавшись на одном корабле с чумными лиссабонцами. Дата отплытия — 5 апреля — приближалась, и Албукерк вынужден был укомплектовывать свои экипажи в тюрьмах, чтобы поход вообще состоялся. В итоге под командой Албукерка собрались неуправляемые буяны, имевшие, помимо ненависти к мусульманам, опыт жестоких преступлений. Руководить такими было непросто. Албукерк жаловался, что на его судах происходит больше ножевых драк, чем во всей Саламанке. В назначенный день Албукерка ожидала еще одна неприятность: его штурман, опытный мореход по имени Жуан Диаш де Солиш, не явился к отбытию. Накануне он убил свою жену и сбежал за границу в Испанию. Тогда Албукерк, бывший чрезвычайно высокого мнения о своих талантах, решил, что обойдется и без штурмана. «Мне не нужен штурман, — заявил он, — я сам поведу свой корабль в Индию».
Две недели спустя Лиссабон охватили беспорядки. Новообращенных христиан из евреев, которым разрешили остаться в городе, обвинили в ереси и распространении чумы. Разъяренные толпы во главе с монахами-францисканцами стали преследовать и убивать евреев на улицах. Во время погрома погибли 200 человек.
Триштан да Кунья доводился Албукерку родней, но гармонии в экспедицию это не вносило. Их отношения были не лучше, чем у Албукерка и его кузена Франсишку в походе 1503 года. Они то и дело вздорили по разным вопросам. Формально командующим был да Кунья, но Албукерк, при его самомнении и тайном губернаторстве, не мог смириться с ролью подчиненного.
В пути португальцев преследовало невезение. Флотилия несколько раз попадала в крупный шторм, а у побережья Африки они едва не разбились о скалы. На Мадагаскаре задержались дольше, чем следовало, поскольку да Кунья вздумал исследовать новый остров, а также в Сомали, где команда увлеклась грабежами. Якобы христианский остров Сокотра в действительности оказался мусульманской твердыней, которую пришлось штурмовать. Попутно выяснили, что для патрулирования входа в Красное море это стратегически бесполезный кусок суши, к тому же бедный ресурсами, где военному гарнизону не прокормиться.
Вместо шести месяцев путешествие растянулось на шестнадцать, и в результате флотилия пропустила навигационный сезон 1506 года и сорвала план доставки пряностей в Лиссабон.
Тем временем морская экспедиция, которую организовал султан Каира, действовала в схожем неторопливом темпе. Командующий Хусейн Мусриф не спешил навстречу франкам, выполняя по пути другие задачи. Прежде всего его занимало строительство оборонительных сооружений вокруг Джедды, куда его назначили губернатором. Исходящие из Лиссабона угрозы захватить Мекку были восприняты настолько серьезно, что целый 1506 год губернатор провел на строительстве. Затем силами армии были подавлены несколько бедуинских восстаний, и лишь в августе 1507 года флот добрался до Адена. К тому времени из двенадцати кораблей осталось только шесть — остальные либо затонули по причине неисправностей, либо были потеряны в сражениях с
