Gajah Mada muncul sebagai seorang pemuka kerajaan sejak masa pemerintahan Jayanegara tahun 1309-1328 Masehi. Karirnya dimulai dengan anggota pasukan pengawal raja (Bayangkari).
Mula-mula beliau menjadi Bekel Bayangkari, setingkat komandan pasukan. Karirnya terus menanjak pada masa Kerajaan Majapahit dilanda beberapa pemberontakan seperti pemberontakan,
- Ranggalawe tahun 1309 M.
- Lembu Sura tahun 1311 M.
- Nambi tahun 1316 M.
- Kuti tahun 1319 M.
Pada tahun 1328 M, raja Jayanegara wafat. Beliau digantikan oleh Tribuanatunggadewi. Dan ketika itu, telah terjadi pemberontakan Sadeng, namun dapat ditumpas oleh Gajah Mada.
Atas jasanya tersebut, Gajah Mada diangkat menjadi Maha Patih Majapahit pada tahun 1334 M. Dalam upacara pengangkatannya tersebut, beliau mengucapkan sumpah untuk menklukkan nusantara di bawah Majapahit.
Sumpah tersebut dikenal dengan nama "Sumpah Palapa".
Gajah Mada tetap menjadi patih mangkubumi ketika Hayam Wuruk naik tahta. Beliau mendampingi raja Hayam Wuruk dalam menjalankan roda pemerintahan.
Pada masa inilah Majapahit mengalami masa-masa emas serta kejayaan. Wilayah Majapahit meliputi,
- Hampir seluruh jawa,
- Sebagian besar pulau Sumatera,
- Semenanjung Malaya,
- Kalimantan,
- Dan Indonesia bagian timur hingga Papua.