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