Kotimaasta saapui kaksi uutta laivuetta ja verestä väkeä. Kun ensinnä Kotshinia oli autettu samudrinia vastaan, joka sitä ahdisti, niin lähdettiin uudelleen Goaa vastaan. Sitä ennen kuitenkin pidettiin sotaneuvottelu, jossa suuri osa kapteeneista, Magalhães muitten mukana, vastusti Goan retkeä, koska sen kautta kauppalaivain paluumatka myöhästyisi. Mutta kapteeniensa vastarinnasta huolimatta Albuquerque päätti sen toteuttaa. Magalhãesille hän tämän vastarinnan vuoksi niin suuttui, että antoi hänestä kotimaahan kuninkaalle epäedullisen lausunnon, jonka vuoksi tämä purjehtija sitten, kun kaikki tiet Portugalin palveluksessa olivat häneltä suljetut, muutti Espanjaan.
Marraskuussa portugalilainen laivasto uudelleen saapui Goan edustalle, mukanaan 1600 miestä. Viipymättä Albuquerque kävi hyökkäykseen ja muutaman päivän kuluttua linna oli vallotettu; mutta Kalikutin tuhoisasta kokemuksesta viisastuneena Albuquerque ei laskenut väkeään hajalle kaupunkia ryöstämään, ennenkuin se oli kahdelta puolelta hyökäten vallotettu. Suuri osa asukkaista pääsi pakoon, mutta kiireessä oli heitä monta tuhatta hukkunut mataliin kanaviin. Kaikki muhamedilaiset surmattiin ilman armoa, miehet, vaimot ja lapset. Eräs moskea, johon oli paennut paljon ihmisiä, sytytettiin palamaan, niin että kaikki siinä olijat saivat surmansa. Albuquerque rakennutti Goaan vahvan kivilinnan, joka sai Manuelin nimen. Sen suojassa saattoivat Portugalilaiset sitten turvallisesti odottaa Bijapurin shahin uusia yrityksiä paikan takaisin vallottamiseksi.
Goan vallotus teki lähiseutujen ruhtinaihin syvän vaikutuksen, jonka vuoksi he nyt pyrkivät mahtavan kenraalikapteenin ystävyyteen. Kambayan kuningas vapautti ilman ehtoja vankeudesta Albuquerquen toisen veljenpojan, Affonso de Noronhan, ja antoi luvan linnan rakentamiseen Diuhun. Joka puolelta, kaukaa sisämaastakin, saapui lähetystöjä vakuuttamaan rauhallisuuttaan ja sopimaan kauppayhteyksistä. Egyptin sulttaanin lähettiläs sai palata Intiasta tyhjin toimin takaisin Kairoon, eikä hänen herransakaan yrittänyt sen koommin lähettää Intian vesille uutta laivastoa. Goa oli ensimäinen paikka Intiassa, jonka Portugalilaiset anastivat omaksi alueekseen. Sen linnan suojiin kohosi paljon portugalilaisia hengellisiä ja hallintorakennuksia ja siellä muun muassa ruvettiin leimaamaan erikoista rahaa. Albuquerque ei kuitenkaan tyytynyt tähän saavutukseen, vaan alkoi viipymättä suunnitella uusia yrityksiä.
Malakan vallotus.
Hän kiinnitti nyt huomionsa Malakkaan, Taka-Intian tärkeimpään kauppakeskustaan, sillä ilman sen omistamista oli mahdoton vallita maustekauppaa, koska maurien laivat olivat alkaneet purjehtia suoraan sinne, välttäen kokonaan Etu-Intian satamia.
Syyskuussa v. 1509 lähti Kotshinista matkaan Diogo Lopez de Sequeira viidellä laivalla. Mukana olivat Magalhães ja Serrão; jälkimäinen myöhemmin purjehti aina Molukeille saakka. Sequeira purjehti Ceylonin ja Nikobarien saarien kautta Sumatran pohjoiselle rannikolle, sillä Sumatrasta saatiin siihen aikaan enin pippuria. Vihdoin hän onnellisesti saapui Malakkaan. Sielläkin maurit koettivat kaikin tavoin vahingoittaa Portugalilaisia; mutta Malakan sulttaani oli heitä kohtaan toistaiseksi ystävällinen, vaikka olikin tunnettu julmuriksi.
Malakassa oleskeli paljon kiinalaisia. Nämä osottivat Portugalilaisille ystävyyttä. Portugalilaiset nyt ensi kerran kohtasivat Keskustan valtakunnan alamaisia. Heidän verraten vaalea ihovärinsä, heidän luottavuutensa — he soutelivat yhtä pelkäämättä portugalilaisten kuin aasialaistenkin aluksien luo — monet heidän tavoistaan ja puvutkin Portugalilaisten mielestä muistuttivat enemmän Länsimaita kuin kaukaista Itää. Ja ennen kaikkea — Kiinalaiset eivät olleet muhamedilaisia. On myös muistettava, etteivät Kiinalaiset siihen aikaan vielä käyttäneet palmikkoja. Jotkut portugalilaiset kirjailijat vertaavat kiinalaisia flaamilaisiin tai alasaksalaisiin. Heissä ei ollut kastihenkeäkään, niinkuin Intian braamanoissa, koska he empimättä söivät kristittyjen kanssa samoista astioista. Näiltä uusilta ystäviltään Portugalilaiset heti alussa saivat varotuksen, ettei heidän pitänyt liiaksi uskoa malaijeihin. Eikä kauaakaan kulunut, ennenkuin maurit saivat sulttaanin suostumaan salajuoneen, jonka kautta Portugalilaiset olivat yhdellä kerralla äkkiä tuhottavat. Ensinnä aiottiin murhata ylipäällikkö itse upseereineen suurissa juhlapidoissa, mutta Sequeira epäsi kutsun, syyttäen pahoinvointia. Sitten aiottiin houkutella portugalilaisia osastolta eri osiin kaupunkia muka ruokavaroja saamaan, ja tuhota osastot erikseen. Pienillä aluksilla oli samalla käytävä laivain kimppuun, miehistön enimmäksi osaksi ollessa maalla. Onneksi tämä kavala juoni vain osaksi onnistui. Laivoista vartijat huomasivat, että maalla oli syntynyt kahakka, ja laivaväki saattoi siten ajoissa ryhtyä puolustustoimiin. Mutta noin 30 portugalilaista, jotka olivat maalla, joutui joko surman omaksi tai vangiksi. Sequeiralla ei ollut likimainkaan riittävästi voimia käydäkseen muutamalla laivalla niin suuren kaupungin kimppuun, jonka vuoksi hän muutamia vihollisen laivoista upotettuaan palasi Malabar-rannikolle. Kun Goan vallotus tuli Malakassa tunnetuksi, niin aljettiin vangittuja Portugalilaisia kohdella paremmin, mutta vapaiksi he pääsivät vasta kun Albuquerque vallotti Malakan.
Albuquerquen tarkotus oli ensinnä, kotimaastaan saamansa ohjeen mukaan, purjehtia melkoisella laivastolla Punaiselle merelle sulkeakseen sen kokonaan muhamedilaisilta, mutta kun monsuuni oli vastainen, niin hän käänsikin laivastonsa sen mukana itää kohti ja purjehti yhdeksällätoista laivalla Malakkaan. Sotaväkeä oli mukana 800 portugalilaista ja 600 miestä intialaista apuväkeä.
Malakka oli aikaisemmin kuulunut Siamiin. Singapur, jonka maine oli vanhempi, oli vähitellen jäänyt takapajulle Malakan rinnalla, kun muhamedin usko oli siellä tullut vallitsevaksi ja kauppa maurien kanssa kehittynyt. Malakka oli samalla kokonaan irtautunut Siamista. Käyttäen taitavasti hyväkseen oivallista kauppa-asemaansa Malakka oli rikastunut ja sen sulttaani oli saattanut rakentaa itselleen suuren sotalaivaston. Kiinalla, Javalla, Kambaylla ja Bengalilla oli Malakassa omat satamamestarinsa, jotka valvoivat kukin maansa kauppaetuja. Malakan kauppasuhteet ulottuivat aina Japaniin saakka. Sinne saapui kaikista ympärillä olevista maista tavaroita ja kauppiaita, Siamia lukuun ottamatta. Siam oli yhä edelleenkin sulttaanin kanssa sotakannalla. Malakan sulttaanin valtakunta kuitenkin oli vain pieni. Se käsitti osan Malakan niemimaan rantoja, mutta ei ulottunut kauaksikaan maan sisään.
Malakan asema on erittäin edullinen senkin vuoksi, että se on eri monsuunialueitten rajalla, sillä Kiinan meressä vallitsevat toiset monsuunit kuin Intian meressä, jonka vuoksi sekä Kiinan että Arabian ja Intian kauppiailla oli Malakkaan purjehtiessaan sopivat vuodenaikaiset tuulet. Kaupungin rintama oli Sumatran ja Malakan niemimaan välisen salmen rannalla; sen vesirintama oli enemmän kuin puolen peninkulman mittainen. Kaupungin läpi juoksi joki, jonka poikki oli silta.