Были приняты меры, чтобы ускорить снаряжение эскадры д'Альмейды. Он отплыл из Португалии в марте 1505 года с двадцатью двумя кораблями. Половине их предстояло возвратиться обратно с индийскими товарами, а остальные одиннадцать оставались в Индийском океане в распоряжении вице-короля. Помимо матросов, на кораблях ехали 1 500 бойцов.
Уже на африканском побережье д'Альмейда начал проводить в жизнь планы Дом Васко. Ловко вмешавшись в династические распри в Килоа, он изгнал одного эмира и посадил другого, и от своего ставленника добился права соорудить в Килоа форт. Д'Альмейда построил на острове Килоа хорошо укрепленную крепость, оставил там 550 человек гарнизона, бригантину, каравеллу и поплыл к Момбассе.
Момбасские власти попытались не допустить высадки португальцев; тогда д'Альмейда напал на Момбассу и сжег город до основания. Были построены еще форты в Мозамбика и Софале.
Так португальцы закрепляли свое влияние на африканском побережье. В Мелинди и Софале правили дружественные португальцам царьки, Момбасса была разрушена, а в Килоа сидел португальский гарнизон. Д'Альмейда пересек Индийский океан и соорудил форт на острове Анжедива. Потом он поспешил в Кочин, который избрал местопребыванием португальских властей в Индии. В Кочине д'Альмейда короновал специально привезенной из Португалии золотой короной молодого раджу, наследовавшего старику, другу португальцев.
Из Кочина д'Альмейда начал исподволь укреплять португальское могущество в Индии. Он вступил в переговоры с раджой самого сильного южноиндийского царства Вижайянагар и послал экспедицию на юг в поиски Маледивских островов. Португальцы не нашли Маледивских островов, но зато случайно открыли дорогу на Цейлон, откуда мавры привозили корицу.
Создав несколько укрепленных пунктов на западном и восточном побережьях Индийского океана, д'Альмейда решил, что увлекаться захватом новых территорий не следует. Выше всего он ставил могущество на море и думал, что захваченные земли только отвлекут внимание и силы португальцев от их прямой задачи – укрепления господства на море. Он советовал королю Маноэлю заключить союзы с индусами против мусульман и охотно пользовался услугами индусского пирата Тиможа, про которого д'Альбукерк говорил, что он «возвысился от пиратства до высоких почестей».
Д'Альмейда писал Маноэлю, что португальцам следует наладить прежде всего торговлю самыми прибыльными товарами – перцем, рабынями, шелком, конями – и заканчивал письмо следующим советом: «Морское могущество превыше всего. Избегайте захвата новых земель, не стройте новых крепостей, кроме тех случаев, когда это совершенно необходимо для защиты ваших факторий от внезапного нападения. Мы не можем тратить на это наших моряков».