Mandailing utawi "Mandahiling" dipunprakirakaken asal saking tembung "Mandala" lan Holing, ingkang ateges sawijining wewengkon Karajan Kalinga. Karajan India mau dipunprakirakaken sampun damel sawijining golongan wiwit abad angka 12, ingkang dumunung saking laladan Portibi dumugi Pidoli. Wonten ing Basa Minangkabau, Mandailing gadhah teges minangka "mande hilang" ingkang ateges "ibu ingkang ical". Amargi makaten wonten ugi pamanggih ingkang ngandharaken bilih masarakat Mandailing asalipun saking Karajan Pagaruyung ing Minangkabau.