Mandailing atau Mandahiling berdasarkan Surat Tumbaga Holing (Serat Tembaga Kalinga) berasal dari kata Mandala (pusat federasi) dan Hiling atau Holing. Wilayah ini kemudian masuk ke dalam kedatuan Sriwijaya setelah Kerajaan Hindu Kalinga berhasil ditumbangkan. Setelah itu, Mandailing berpindah-pindah kekuasaan dari satu dinasti ke dinasti lainnya.