Kisah kelahiran Gajah Mada dipenuhi dengan mitos. Terdapat dugaan bahwa pemitosan kelahiran Gajah Mada tersebut ditujukan untuk melegitimasi kedudukannya sebagai orang besar, orang sakti, dan sebagai pahlawan Majapahit karena berhasil menundukkan banyak wilayah di nusantara demi terealisasinya Sumpah Palapa.
Kitab Usana Jawa mengisahkan bahwa Gajah Mada tidak lahir dari manusia, melainkan lahir begitu saja dari buah kelapa. Barangkali pemitosan tersebut berangkat dari dua kata "kelapa" dan "palapa" yang hampir sama dalam pengucapannya. Sungguhpun demikian, pemitosan tersebut tidak masuk akal. Mengingat belum ada manusia yang lahir di dunia ini dari buah kelapa. Kalau toh ada, manusia tersebut lahir dari negeri dongeng.
Sementara, Babad Gajah Maddha menyebutkan bahwa Gajah Mada merupakan anak dari Dewa Brahma -- salah satu dari tiga dewa utama (Trimurti) kaum Hindu -- dengan Nariratih, istri seorang pendeta muda bernama Mpu Sura Dharmayogi. Dengan demikian, pemitosan ini mirip dengan pemitosan Ken Arok yang merupakan putra Brahma. Perbedaannya, Gajah Mada hidup di zaman Majapahit dan berstatus sebagai Mahapatih Amangkubhumi. Sementara, Ken Arok, menurut Serat Pararaton, hidup di zaman Tumapel (Singhasari) dan berstatus sebagai raja.
Kisah-kisah kelahiran Gajah Mada yang berbau supranatural ini lazim tercatat dalam naskah-naskah babad dengan tujuan bahwa kelahiran tersebut memang direstui oleh Dewata untuk mendapat kekuatan adi kodrati. Pengertian lain, proses kelahirannya sudah menandakan bahwa Gajah Mada ditakdirkan menjadi orang yang sangat tersohor atau disegani baik oleh masyarakat dalam negeri Majapahit maupun masyarakat mancanegara.
Selain kelahiran Gajah Mada yang diwarnai dengan mitos, silsilahnya pun tidak jelas. Menurut Babad Arung Bondan, Gajah Mada disebutkan sebagai putra dari patih Majapahit. Sementara Agus Aris Munandar menduga bahwa Gajah Mada merupakan putra Gajah Pagon, pengawal setia Dyah Wijaya, Raja Majapahit I yang membuka hutan Tarik. Cikal bakal Kerajaan Majapahit.
Menurut Serat Pararaton bahwa Gajah Pagon dan Gajah Mada memiliki sifat yang sama yakni pemberani, tahan mental, tidak mudah menyerah, setia kepada tuannya, dan berperilaku seperti hewan gajah yang bernyali untuk menghadang segala rintangan.
Kata "gajah" pada nama Gajah Mada mengacu pada hewan yang dalam mitologi Hindu dipercaya sebagai vahana (hewan tunggangan) Dewa Indra. Sementara, gajah milik Dewa Indra bernama Airavata. Sedangkan "mada" pada nama Gajah Mada yang berasal dari bahasa Jawa Kuna tersebut mengandung makna "mabuk".
Dari uraian di muka bisa disimpulkan bahwa nama Gajah Mada mengandung pengertian gajah mabuk. Maka, ia akan berjalan seenaknya, beringas, dan menerabas segala macam rintangan. Sepertinya nama itu yang cocok dan sudah dipikirkan betul-betul sebelum diberikan kepada Gajah Mada.
Sumber lain juga menyebutkan bahwa nama Gajah Mada bukan nama asli, melainkan nama gelar. Sebelum menjabat sebagai Mahapatih Amangkubhumi, Gajah Mada dikenal dengan Jaka Mada. Nama ini pun bukan nama asli, melainkan nama yang menunjukkan bahwa ia merupakan seorang pemuda dari wilayah Mada. Namun sampai sekarang, wilayah Mada pun masih menjadi perdebatan di kalangan sejarawan.
Dari uraian di muka, muncul pendapat bahwa tokoh Gajah Mada masih misterius. Kebenaran atas keberadaan tokoh tersebut sejak masa pemerintahan Jayanagara, Tribhuwana Wijayatunggadewi, hingga Hayam Wuruk masih belum terkuak dengan jelas.
Sumpah Palapa dan Wilayah Kekuasaan Majapahit