Perebutan Melaka (1511)
Kontak pertama dengan Portugis

Lukisan cat air Portugis dari orang Melayu di Malaka, sekitar tahun 1540, ditampilkan dalam Códice Casanatense
Ilustrasi pasangan Melayu, dari , antara tahun 1669 dan 1682
Tidak terkesan dengan kurangnya hasil Almeida, pada April 1508, Raja Manuel mengirim armada langsung ke Malaka, terdiri dari empat kapal di bawah komando Diogo Lopes de Sequeira, yang juga ditugaskan untuk memetakan Madagaskar dan mengumpulkan informasi tentang Cina. Sequeira menerima perintah kerajaan yang secara khusus menginstruksikannya untuk mendapatkan izin untuk membuka pos perdagangan secara diplomatis dan berdagang secara damai, tidak menanggapi provokasi apa pun dan tidak melepaskan tembakan kecuali jika ditembaki:
Kami memerintahkan dan memerintahkan agar Anda tidak melakukan kerusakan atau kerugian di semua bagian yang Anda jangkau, dan sebaliknya semua harus menerima kehormatan, bantuan, keramahan, dan perdagangan yang adil dari Anda, karena layanan kami sangat menuntutnya di awal ini. Dan meskipun sesuatu mungkin dilakukan terhadap Anda dalam usaha Anda, dan Anda mungkin berhak untuk menyebabkan kerusakan, tutupi itu sebaik mungkin, menunjukkan bahwa Anda tidak menginginkan perdamaian dan persahabatan, karena kami menuntutnya dari Anda. Namun jika Anda diserang, atau ditipu sedemikian rupa sehingga tampak bagi Anda bahwa mereka ingin menyakiti Anda, maka Anda harus melakukan semua kerusakan dan kerugian yang Anda bisa kepada mereka yang berusaha melakukannya terhadap Anda, dan tidak situasi lain akan Anda lakukan perang atau bahaya.
Pada April 1509, armada berada di Cochin dan Raja Muda, Dom Francisco de Almeida, memasukkan kerakah lain ke dalam armada untuk memperkuatnya. Keputusan itu tidak sepenuhnya tidak bersalah, karena di atas kapal melakukan perjalanan beberapa pendukung saingan politik Almeida, Afonso de Albuquerque. Di antara awaknya juga ada Ferdinand Magellan.
Dalam perjalanannya ia diperlakukan dengan baik oleh raja-raja Pedir dan Pasai yang mengiriminya hadiah. Sequeira mendirikan salib di kedua tempat mengklaim penemuan dan kepemilikan. Dia membuang sauh di pelabuhan Malaka, di mana dia menakuti orang-orang dengan bunyi meriamnya yang seperti petir, sehingga setiap orang bergegas naik ke kapal mereka untuk berusaha mempertahankan diri dari tamu baru dan tidak diinginkan ini. Sebuah perahu datang dengan pesan dari kota, untuk menanyakan siapa mereka.
Ekspedisi tersebut tiba di Malaka pada bulan September 1509 dan segera Sequeira berusaha menghubungi para saudagar Cina di pelabuhan. Mereka mengundangnya naik salah satu jung dagang mereka dan menerimanya dengan sangat baik untuk makan malam dan mengatur pertemuan dengan Sultan Mahmud. Sultan segera memberikan izin kepada Portugis untuk mendirikan feitoria dan menyediakan gedung kosong untuk tujuan itu. Waspada terhadap ancaman Portugis terhadap kepentingan mereka, namun komunitas pedagang kuat Muslim Gujarat dan Jawa meyakinkan Sultan Mahmud dan Bendahara untuk mengkhianati dan menangkap Portugis.
Sequeira sementara itu begitu yakin akan keramahan Sultan sehingga dia mengabaikan informasi bahwa Duarte Fernandes, Kristen Baru yang berbicara bahasa Parsi, diperoleh dari pemilik penginapan Persia tentang persiapan yang sedang berlangsung untuk menghancurkan armada, mengkonfirmasi bahkan oleh para saudagar Cina. Dia sedang bermain catur di atas kapal andalannya ketika armada Melayu, yang menyamar sebagai pedagang, menyergap kapal-kapal Portugis. Portugis menolak setiap upaya naik, tetapi dihadapkan dengan banyaknya kapal Melayu dan tidak dapat mendaratkan pasukan apa pun untuk menyelamatkan orang-orang Portugis yang telah tinggal di feitoria, de Sequeira membuat keputusan untuk berlayar kembali ke India sebelum musim hujan dimulai dan membuat mereka benar-benar terjebak di Asia Tenggara. Sebelum berangkat ia mengirim pesan kepada Sultan dan bendahara berupa dua tawanan masing-masing dengan anak panah menembus tengkoraknya sebagai kesaksian tentang apa yang akan terjadi pada mereka jika 20 orang Portugis yang menyerah dilukai.