Ulah Mahapati membuka jalan bagi Kuti untuk melakukan kudeta terhadap Raja Jayanegara. Namun berkat upaya anggota bekel bhayangkari (pasukan pengawal raja) bernama Gajah Mada, Kuti berhasil dibunuh, sementara raja dapat diselamatkan. Sebagai anugerah dari raja, Gajah Mada kemudian diangkat menjadi patih di Kahuripan, selanjutnya di Daha sebagaimana disebutkan dalam Prasasti Palungan (1330) dan Prasasti Batur (angka tahunnya tidak terbaca).
Selama menjadi pimpinan bhayangkari, Gajah Mada berhasil menumpas beberapa pemberontakan di Kerajaan Majapahit. Berkat pasukan bhayangkari pula, Kerajaan Majapahit mampu meluaskan ekspansinya ke luar Jawa hingga ke mancanegara. Karena prestasinya itu, Gajah Mada kemudian dinaikkan jabatannya menjadi Mahapatih.
Tindakan yang pertama kali dilakukan Gajah Mada sejak menjadi mahapatih adalah memperkuat angkatan perang kerajaan, baik di daratan maupun di lautan. Selain itu, untuk memajukan kesejahteraan negara, Gajah Mada membentuk jawatan-jawatan yang sebelumnya tidak dikenal. Yang paling populer adalah Jawatan Pekerjaan Umum, dengan tugas utama memelihara dan membangun candi, keraton, dan gedung pemerintah.
Demikian juga dengan pembentukan Jawatan Pengadilan. Fungsi jawatan ini adalah untuk benar-benar menegakkan supremasi hukum. Diberitakan bahwa Jawatan Pengadilan selalu bahu-membahu dengan pasukan bhayangkari. Hal ini didukung oleh penegakan hukum yang benar-benar berdasarkan undang-undang. Bahkan setiap sidang dipimpin oleh para pengadil yang paham betul akan kitab sastra, sekaligus kitab hukum dan kitab keagamaan.
Kitab hukum
Di bawah Gajah Mada, Kerajaan Majapahit benar-benar menegakkan hukum. Hal ini bisa dilihat dari informasi sejumlah data tekstual atau sumber tertulis, seperti prasasti dan naskah kuno. Majapahit kelak akan menjadi cikal bakal negara Indonesia seutuhnya.
Menurut sumber-sumber tertulis itu, siapa yang bersalah akan dihukum dan dijerat dengan undang-undang yang bertumpu pada Kutaramanawadharmmasastra. Meskipun berasal dari India, undang-undang itu dipandang sangat bermanfaat untuk masyarakat. Undang-undang lokal juga dibuat, yang terjemahannya dipublikasikan oleh Prof. Slametmuljana (Perundang-undangan Madjapahit, 1967). Selama beberapa abad Kerajaan Majapahit maju pesat dan terkenal sampai mancanegara.
Menurut sejumlah prasasti dan naskah kuno pula, struktur pemerintahan dan birokrasi pada zaman Kerajaan Majapahit tergolong lengkap dan teratur. Struktur pemerintahan di sana mencerminkan adanya kekuasaan yang bersifat teritorial dan disentralisasikan dengan birokrasi yang terinci. Hal demikian terjadi karena adanya pengaruh kepercayaan yang bersifat kosmologi. Berdasarkan konsepsi itu, maka seluruh Kerajaan Majapahit disamakan dengan dewa tertinggi yang bersemayam di puncak Mahameru.
Artinya demikian, wilayah Kerajaan Majapahit yang terdiri atas negara-negara daerah, disamakan dengan tempat tinggal para dewa Lokapala yang terletak di keempat penjuru mata angin. Raja yang dianggap sebagai penjelmaan dewa di dunia memegang otoritas politik tertinggi dan menduduki puncak hierarki kerajaan. Dalam melaksanakan pemerintahan, raja dibantu oleh sejumlah pejabat birokrasi. Kelompok paling terkenal bernama bhatāra saptaprabhu yang merupakan sebuah pahom narendra, yaitu suatu lembaga yang merupakan “Dewan Pertimbangan Kerajaan” sebagaimana disebutkan Kidung Sundayana dan Kitab Nagarakretagama (Sejarah Nasional Indonesia II, 1984).
Bhatāra saptaprabhu beranggotakan keluarga kerajaan. Pada masa pemerintahan Hayam Wuruk, yang menjabat sebagai Dewan Pertimbangan Kerajaan adalah raja, permaisuri, ayah-bunda raja, paman raja, dua adik perempuan raja beserta suaminya.
Pejabat lain yang mendukung pemerintahan adalah “Dewan Menteri” yang berfungsi sebagai “Badan Pelaksana Pemerintahan”. Di bawahnya ada Dharmmodhyaksa, yakni pejabat tinggi kerajaan yang bertugas menjalankan fungsi yurisdiksi keagamaan. Pejabat-pejabat itu dikelompokkan dalam dua golongan, yaitu golongan untuk urusan agama Buddha dan golongan untuk urusan agama Siwa (Hindu).
