In 1506 word hy aangestel as bevelvoerder van 'n vloot van 15 skepe wat na die ooskus van Afrika en buite Indië gestuur is. Sy neef, Alfonso d' Albuquerque, was in beheer van 'n eskader van vyf vaartuie in hierdie vloot wat daarna op hul eie gegaan het. Hulle missie was om Sokotra-eiland te verower en 'n vesting daar te bou in die hoop om die handel in die Rooi See te beheer. Hulle vaar saam totdat hulle Mosambiek bereik het. In die Mosambiekkanaal vind hulle sy vriend kaptein João da Nova wat daar gestrand was na sy terugkeer uit Indië. Hulle het hom en die skip Frol de la mar gered, wat albei by die vloot aangesluit het. Na 'n reeks suksesvolle aanvalle op Arabiese stede aan die ooskus van Afrika, is hulle na Sokotra.
Nadat hy die oorlog met die Ajuran-ryk verloor het oor die mislukte poging om Barawa te beset, het hy besluit om sy manskappe op die Sokotra-eilande te hergroepeer en na Mogadishu te vaar, wat die rykste stad in Afrika was. Maar daar is 'n woord versprei oor wat in Barawa gebeur het, en 'n groot mobilisering van die troepe het plaasgevind. Baie ruiters, soldate en oorlogskepe in verdedigingsposisies het nou die stad bewaak. Nietemin het Tristão steeds gekies om na die stad te gaan en te probeer verower, hoewel verskeie offisiere en soldate in sy leër dit teengestaan het, uit vrees vir 'n nederlaag. Hy het wel uiteindelik besluit om die Somaliërs in vrede te laat nadat hy besef het dat hulle buitengewoon moeilik sal wees om te onderdruk en dat dit 'n groter mobilisasie sou verg, wat toe die Ajuran-ryk onafhanklik sou gelaat het.
Die groot, luukse diplomatieke sending van honderd-en-veertig persone het sy weg deur Alicante en Majorka gemaak en in Februarie by die buitewyke van Rome aangekom. Hulle het op 12 Maart 1514 die strate van Rome geloop in 'n buitengewone optog van eksotiese natuurlewe en rykdom van Indië, met baie geklee in 'Indiese styl'. Die optog bevat 'n olifant met die naam Hanno, 'n geskenk aan die pous, en twee en veertig ander diere, waaronder twee luiperde, 'n panter, 'n paar papegaaie, kalkoene en skaars Indiese perde. Hanno het 'n silwerplatform op die rug gedra, gevorm as 'n kasteel met 'n kluis met koninklike geskenke, insluitend baadjies geborduur met pêrels en edelstene, en goue muntstukke vir die geleentheid. Die pous het die optog in die Castel Sant'Angelo ontvang. Die olifant het drie keer in eerbied neergekniel en dan, na 'n teken van sy Indiese mahout (bewaarder), sy slurp gebruik om water uit 'n emmer te suig en dit oor die skare en die kardinale te spuit.
Teen 29 April 1514 het die Portugese hul geld uitgeput, maar hulle het 'n onderneming gesoek wat deur die pous onderteken is, wat ryk geskenke aan koning Manuel teruggestuur het. Die koning het geantwoord met 'n skip vol speserye en later 'n Indiese renoster van die sultan Muzaffar Shah II van Gujarat na hom gestuur. Die boot wat dit vervoer het, is vroeg in Februarie 1516 by Genua verwoes, en die Renoster is in 1515 deur Albrecht Dürer in sy baie beroemde renosterhoutuitsneewerk uitgebeeld.