Pada tahun 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 kemudian diangkat secara resmi oleh Ratu Tribhuwanatunggadewi sebagai patih di Majapahit (1334).
Sumpah Palapa
Pada waktu pengangkatannya ia mengucapkan Sumpah Palapa, yakni ia baru akan menikmati palapa atau rempah-rempah yang diartikan kenikmatan duniawi jika telah berhasil menaklukkan Nusantara. Sebagaimana tercatat dalam kitab Pararaton berikut [1]: “ 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, Tañjungpura, 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 pemerintahan Prabu Hayam Wuruk (1350-1389) yang menggantikan Tribhuwanatunggadewi, Patih Gajah Mada terus 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
Dalam Kidung Sunda[2] diceritakan bahwa Perang Bubat (1357) bermula 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. Gajah Mada yang menginginkan Sunda takluk, memaksa menginginkan Dyah Pitaloka sebagai persembahan pengakuan kekuasaan Majapahit. Akibat penolakan pihak Sunda mengenai hal ini, terjadilah pertempuran tidak seimbang antara pasukan Majapahit dan rombongan Sunda di Bubat; yang saat itu menjadi tempat penginapan rombongan Sunda. Dyah Pitaloka bunuh diri setelah ayahanda dan seluruh rombongannya gugur dalam pertempuran. Akibat peristiwa itu, Patih Gajah Mada dinonaktifkan dari jabatannya.
Dalam Nagarakretagama diceritakan hal yang sedikit berbeda. Dikatakan bahwa Hayam Wuruk sangat menghargai Gajah Mada sebagai Mahamantri Agung yang wira, bijaksana, serta setia berbakti kepada negara. Sang raja menganugerahkan dukuh “Madakaripura” yang berpemandangan indah di Tongas, Probolinggo, kepada Gajah Mada. Terdapat pendapat yang menyatakan bahwa pada 1359, Gajah Mada diangkat kembali sebagai patih; hanya saja ia memerintah dari Madakaripura.
Akhir hidup
Disebutkan dalam Negarakretagama bahwa sekembalinya Hayam Wuruk dari upacara keagamaan di Simping, ia menjumpai bahwa Gajah Mada telah gering (sakit). Gajah Mada disebutkan meninggal dunia pada tahun 1286 Saka atau 1364 Masehi.
Hayam Wuruk kemudian memilih enam Mahamantri Agung, untuk selanjutnya membantunya dalam menyelenggarakan segala urusan negara.