Tidak ada satu sumber pun yang dapat dijadikan rujukan untuk mengetahui asal Gajah Mada dan siapa orang tuanya.Para sejarawan bersilang pendapat tentang asal usulnya.Ada yang menyebut Gajah Mada berasal dari Sumatera, tepatnya dari Minangkabau dengan asumsi bahwa kata Mada itu di Minangkabau berarti bandel, sementara diJawa tidak ada kata Mada dalam kosa kata bahasanya.Selain itu gelar Gajah juga diambil dari asal nama binatang yang berada di pulau andalas itu.Asumsi ini diperkuat dengan kedekatan hubungan antara Gajah Mada dan Adityawarman (pendiri kerajaan Pagaruyung), seorang pangeran Majapahit berdarah Sumatera, kemungkinan Adityawarman lah yang membawa Gajah Mada ke Majapahit.Namun sebagian lainnya menyebut Gajah Mada berasal dari Bali.Masyarakat Bali mempercayai cerita turun temurun yang menyebut bahwa ibu sang patih ini berasal dari Bali.Ada juga yang memperkirakan Gajah Mada berasal dari suku Dayak Krio di Kalimantan Barat, merujuk dari kisah nenek moyang suku Krio tentang seorang Panglima besar dayak bernama Panglima Jaga Mada yang diutus ke Jawa Dwipa untuk menguasai tanah Jawa.Kemudian ada juga yang menyebut bahwa Gajah Mada itu berasal dari Mongol.Diperkirakan dia adalah salah satu pimpinan pasukan Mongol yang tertinggal.Ketika itu Raden Wijaya (pendiri Majapahit) mengalahkan pasukannya yang berniat menyerang Raja Kertanegara karena telah melecehkan Mongol dengan memotong telingan Meng Khi (utusan Mongol).