Гоа бива превзета с атака, но не било съдено на д’Албукерке да се радва дълго на своята победа. Многобройни индийски войски обкръжават града и застрашават да отрежат пътя на португалците за изтегляне към корабите. И пак единствен изход остава бързото бягство. То се изкупува с много жертви. Загубват един кораб, 30 души попадат в плен. Магаляиш отново съветва да се върнат в родината. И отново д’Албукерке грубо отхвърля това предложение. Той се връща в Кочин и заварва там 11 кораба, които Диего де Вашко Гонселес и Гонсалу де Секейра са докарали от Португалия в Индия. Това подкрепление, дошло толкова навреме, още повече утвърждава намерението на д’Албукерке. Той свиква военен съвет на капитаните и всички с изключение на Магаляиш подкрепят идеята да се атакува Гоа отново. Гоа трябва да принадлежи на Португалия, защото който притежава този град, ще владее пътищата за Ормуз и Аден, дори цялото Западно море.12 Възражението на Магаляиш, че даже и победата ще направи завръщането в Лисабон невъзможно, тъй като ще пропуснат мусона, благоприятен за обратния път към родината, бива отхвърлено от д’Албукерке с думите: „И след като подчиня Гоа, аз няма да се върна, преди да бъде завладяна Индия.“
На 24 ноември 1600 португалци отново нападат Гоа. Още на другия ден крепостта пада, а на следващия и градът. Всички жители, включително жени и деца, биват избити. Индийската обсадна войска, която бързо се приближава, е разбита и унищожена. Покоряването на Гоа има за последица нещо, на което д’Албукерке не се е надявал и в най-смелите си мечти: цяла Индия се предава. Чудовищният звяр Португалия не може да бъде убит. Разрушен ли е един кораб, три други се появяват от неизвестна посока. Убиеш ли един португалец, петима други излизат на негово място. По-добре е да се намери път за разбирателство.
Султанът на Диу неочаквано заявява, че иска да живее в мир и сговор с Португалия и разрешава построяването на една крепост. Султанът на Каликут праща скъпи дарове за д’Албукерке. Владетелят на Биснага също изявява желание да установи търговски връзки с Португалия. И владетелите на областите от вътрешността уверяват д’Албукерке, че никога не са и помисляли да смятат него и другарите му за врагове.
Д’Албукерке не се задоволява с това. Той мисли за града, за който Секейра му е разказвал. Арабските търговски кораби, заобикаляйки Индостан, поемат пътя към Червено море, това той знае отдавна. Следователно сам трябва да тури ръка на най-големия пазар за подправки във вътрешността на Индия. Който завладее Малака, ще владее търговията с подправки в целия свят, затова Португалия ще покори Малака. И то благодарение на него, Афонсу д’Албукерке, а някакъв си Магаляиш иска да му попречи да тръгне по пътя, който ще го изведе до славата, властта и парите.
На 1 юли 1511 г. португалските кораби хвърлят котва в пристанището на Малака. Чрез съгледвачи д’Албукерке узнава, че султанът разполага с осем хиляди оръдия, тридесет хиляди бойци и четиридесет военни слона. Значителна военна сила, но все пак недостатъчна, за да уплаши завоевателя на Гоа, свикнал на бързи победи. Най-напред д’Албукерке иска да му предадат пленниците. Когато султан Махмуд отхвърля молбата му той нарежда да подпалят пристанището и всички къщи по брега. Тогава освобождават пленниците. Но д’Албукерке вече не може да се задоволи с това. Той, който досега не е претърпял никакви щети, иска обезщетение и то толкова високо, че дори богатата Малака не може да го изплати.
Махмуд също е чул за случилото се в Гоа. Той се страхува от португалците и освен това обича мира повече от войната. Повеждат се преговори, разменят се пратеници, двете страни се пазарят, заплашват, дават си взаимни уверения и се перчат една пред друга. Сутринта на 25 юли преговорите се преустановяват и само подир един час д’Албукерке дава знак за нападение на града.
Войските се разделят на две. Едната половина се предвожда от Жоау де Лима, а другата от самия адмирал. Де Лима слиза на сушата недалеч от султанския дворец, а д’Албукерке при единствения мост, който свързва малайската с китайската част на града. Планът му предвижда най-напред да превземе този мост и след това да се съедини с де Лима, без да се страхува, че китайците ще се озоват в гръб. Той не мисли, че синовете на Небесната империя ще влязат в битка с него, защото те са търговци, а не войници.