Pada 1329, Patih Majapahit yakni Aryo Tadah (Mpu Krewes) ingin mengundurkan diri dari jabatannya. Ia menunjuk Patih Gajah Mada dari Kediri sebagai penggantinya. Patih Gajah Mada sendiri tak langsung menyetujui. Ia ingin membuat jasa dahulu pada Majapahit dengan menaklukkan Keta dan Sadeng yang saat itu sedang melakukan pemberotakan terhadap Majapahit. Keta & Sadeng pun akhirnya takluk. Patih Gajah Mada diangkat sebagai patih di Majapahit (1334).
Sumpah Palapa
Pada waktu pengangkatannya ia mengucapkan Sumpah Palapa. Bahwa ia baru akan menikmati palapa atau rempah-rempah yang diartikan kenikmatan duniawi, jika telah berhasil menaklukkan Nusantara. Menjadi Patih Amangkubhumi Majapahit, tahun 1258 Saka (1336 M).
Dalam kitab Pararaton, sumpah palapa itu berbunyi demikian: "Sira Gajah Mada pepatih amungkubumi tan ayun amukti palapa, sira Gajah Mada: Lamun huwus kalah nusantara ingsun amukti palapa, lamun kalah ring Gurun, ring Seram, Tajungpura, ring Haru, ring Pahang, Dompo, ring Bali, Sunda, Palembang, Tumasik, samana ingsun amukti palapa " ("Gajah Mada sang Maha Patih tak akan menikmati palapa, berkata Gajah Mada "Selama aku belum menyatukan Nusantara, aku takkan menikmati palapa. Sebelum aku menaklukkan Pulau Gurun, Pulau Seram, Tanjungpura, Pulau Haru, Pulau Pahang, Dompo, Pulau Bali, Sunda, Palembang, Tumasik, aku takkan mencicipi palapa.")
Walaupun ada sejumlah (atau bahkan banyak) orang yang meragukan sumpahnya, Patih Gajah Mada memang hampir berhasil menaklukkan Nusantara. Bedahulu (Bali) dan Lombok (1343), Palembang, Swarnabhumi (Sriwijaya), Tamiang, Samudra Pasai, dan negeri-negeri lain di Swarnadwipa (Sumatra) telah ditaklukkan. Lalu Pulau Bintan, Tumasik (Singapura), Semenanjung Malaya, dan sejumlah negeri di Kalimantan seperti Kapuas, Katingan, Sampit, Kotalingga (Tanjunglingga), Kotawaringin, Sambas, Lawai, Kandangan, Landak, Samadang, Tirem, Sedu, Brunei, Kalka, Saludung, Solok, Pasir, Barito, Sawaku, Tabalung, Tanjungkutei, dan Malano.
Di zaman Prabu Hayam Wuruk (1350-1389), Patih Gajah Mada mengembangkan penaklukan ke wilayah timur seperti Logajah, Gurun, Sukun, Taliwung, Sapi, Gunungapi, Seram, Hutankadali, Sasak, Bantayan, Luwuk, Makassar, Buton, Banggai, Kunir, Galiyan, Salayar, Sumba, Muar (Saparua), Solor, Bima, Wandan (Banda), Ambon, Wanin, Seran, Timor, dan Dompo.
Perang Bubat
Karier politiknya mulai merosot akibat Perang Bubat (1357). Dalam Kidung Sunda diceritakan bahwa hal ini bermula pada saat Prabu Hayam Wuruk hendak menikahi Dyah Pitaloka putri Sunda sebagai permaisuri. Lamaran Prabu Hayam Wuruk diterima pihak Kerajaan Sunda dan rombongan besar Kerajaan Sunda datang ke Majapahit untuk melangsungkan pernikahan agung itu.
Namun Patih Gajah Mada yang menginginkan Sunda takluk memaksa menginginkan Dyah Pitaloka sebagai persembahan pengakuan kekuasaan Majapahit. Akibat penolakan pihak Kerajaan Sunda mengenai hal ini, terjadilah pertempuran yang tidak seimbang antara pasukan Majapahit dan rombongan Sunda di Bubat yang saat itu menjadi tempat penginapan rombongan Sunda. Dyah Pitaloka sendiri bunuh diri setelah ayahanda beserta seluruh rombongannya gugur dalam pertempuran.
Akibat peristiwa itu, Patih Gajah Mada dinonaktifkan dari jabatannya dan ia diberi pesanggrahan "Madakaripura" di Tongas, Probolinggo. Namun pada 1359, Gajah Mada diangkat kembali sebagai patih, hanya saja ia memerintah dari Madakaripura.
Pada 1364, Gajah Mada menghilang secara misterius dan tidak pernah muncul lagi. Ada beberapa hipotesa tentang Gajah Mada di periode 1364 dan sesudahnya.
Yang pertama, diperkirakan Gajah Mada mengasingkan diri ke Lampung, dan akhirnya meninggal di Lampung. Saat ini ada pusara yang diyakini sebagai petilasan Gajah Mada di Lampung. Yang kedua, ia bergabung dengan Adityawarman yang telah menjadi penguasa Kerajaan Pagaruyung, Kerajaan Dharmasraya, Jambi, dan Palembang. Pada saat tiba di Lampung, ia membuat pusara yang seolah-olah adalah makamnya, supaya tidak dicari oleh Majapahit. Setelah itu ia melanjutkan perjalanannya ke utara dan bergabung dengan Adityawarman.
Yang ketiga, ia memimpin ekspedisi ke seberang lautan hingga ke Madagaskar. Asal muasal pulau tersebut memiliki nama Madagaskar, diperkirakan ada hubungannya dengan Mahapatih Gajah Mada. Penduduk asli pulau itu, etnis Merina dan Betsileo, mirip dengan penduduk asli pulau Jawa. eko risanto
