Nama Nagur berasal dari perpaduan kata "Na + Agur" yang berarti gelar bagi seorang pemimpin yang gagah berani, benar, adil, dan bijaksana. Namun sejumlah sejarawan ada juga yang mengkaitkan nama Nagur dengan Chota Nagpur dan juga kota Nagore yang ada di India. Kerajaan ini berdiri ratusan tahun kemudian sepeninggal Darayad Damadik, terbentuknya kerajaan ini diawali oleh perpaduan sejumlah kampung yang pada suku Simalungun dibagi ke dalam beberapa bagian meliputi huta, nagori, dan urung. Pasca berdirinya kerajaan, dipilihlah suatu lokasi sebagai pusat kerajaan yang disebut dengan pamatang. Nama Nagur pertama kali masuk dalam catatan sejarah yaitu pada almanak (annals) Dinasti Sui (581-618 M) salah satu kekaisaran di Tiongkok penerus dari Dinasti Jin dan peletak dasar bagi kejayaan Dinasti Tang sebagai penggantinya. Almanak tersebut meriwayatkan tentang transaksi perdagangan bilateral antara Nagur dengan Dinasti Sui di perairan sungai Bah Bolon dekat Kota Perdagangan. Sebagaimana hasil penelitian Sutan Martuaraja Siregar, guru sejarah di Normaal School Pematang Siantar, dia melihat Nagur sebagai sebuah Kerajaan Batak yang didirikan orang Simalungun dan menjadi pusat penyembahan berhala (Priests Kingdom of Batak Pagan). Dengan adanya budidaya rambung merah (Sim: balata/Latin: Ficus Elastica) yang dikembangkan masyarakat Nagur, sehingga mengundang bangsa Tiongkok dari Dinasti Sui untuk membeli hasil sumber daya alam Nagur yang dibutuhkan sebagai kedap air (water-tight) bagi kapal-kapal dagang mereka. Pada waktu itulah pihak Tiongkok mendirikan kota pelabuhan Sang Pang To di tepi Sungai Bah Bolon, sekitar 3 Kilometer dari kota Perdagangan sekarang. Mereka banyak meninggalkan batu-batu bersurat di pedalaman Simalungun yang kini telah lenyap akibat penggusuran oleh pembukaan perkebunan dan pabrik-pabrik pada zaman Belanda. Tidak jauh dari tempat ini, ada satu lokasi yang pada zaman dahulu jadi tempat ritual pemujaan roh leluhur bernama Dolog Sinumbah, sebelum kehadiran Belanda di tempat ini terdapat banyak kuil dan candi Buddha, ada satu situs candi yang berhasil diselamatkan pada waktu penggusuran oleh pihak Belanda sewaktu mendirikan pabrik dan perkebunan (situs candi ini kini disimpan oleh keluarga marga Purba di Medan).
Nakhoda Persia, Buzurug bin Shahriyar Al-Ramhurmuzi saat lawatannya ke pulau Sumatera pada tahun 955 M mencatat adanya suatu kerajaan bernama Nakus yang mengacu pada Nagur. Keterangan lainnya juga datang dari Marco Polo (1271-1295), seorang pengembara dari Venesia, Italia pada tahun 1292 pernah mengunjungi sejumlah pulau di pesisir Sumatera, di antaranya adalah Dagroian yang tidak lain adalah Nagur, yang letaknya berada di Pidie (Aceh) sekarang. Marco Polo menceritakan kebiasaan masyarakat Dagroian yang kanibal dan larut dengan praktik genosida. Masyarakatnya benar-benar primitif dan penyembah berhala. Kemudian pada awal abad ke 13 M, Zhao Rugua mencatat sebuah negeri bernama Pa-t’a di bawah kuasa Sriwijaya. Antara Pa-t’a dan Bata sudah diterima umum ada kaitannya dengan Batak. Batak yang dimaksud di sini merujuk pada Nagur, karena pada masa itu Nagurlah satu-satunya kerajaan Batak. Sementara itu, Niccolo de’ Conti seorang pedagang dan penjelajah dari Venesia, Italia pada tahun 1430 berkunjung ke Sumatera dan tinggal selama setahun di kota Sciamuthera (Samudera Pasai) dan pada tahun 1449 dia pertama kalinya menemukan jejak masyarakat benama “Batech”. Dia mengatakan di bagian tertentu di pulau Sumatera terdapat sebuah tempat bernama Batech, penduduknya memangsa daging manusia. Mereka terus-menerus berperang dengan tetangga mereka, tengkorak musuh mereka disimpan sebagai harta kemudian menjualnya untuk memperoleh uang. Lain dari pada itu, Tomé Pires seorang apoteker dan kepala gudang rempah-rempah Portugis di Malaka, dalam karya terbesarnya Suma Oriental (Dunia Timur) yang ditulis pada tahun 1512-1515. Buku tersebut memberikan banyak informasi berharga mengenai keadaan nusantara pada abad ke-16, dia menyebut Sumatera dengan Camotora sebuah daerah yang luas dan makmur terdapat banyak emas, kapur barus, lada, sutera, kemenyan, damar, madu, minyak tanah, belerang, kapas, dan rotan. Selain itu, Sumatera juga memiliki banyak padi, daging, ikan, dan bermacam-macam minyak, tuak termasuk tampoy yang mirip anggur di Eropa. Dia mengatakan Sumatera adalah ibukota dari Pasai. Pires mencatat tiga tempat yang menjadi pusat aktivitas para pedagang asing di pesisir timur, yaitu Batta (di selatan Pasai) yang memiliki komoditi utama rotan, lalu Aru yang memiliki cukup banyak kamper dan kemenyan, dan terakhir Arcat (antara Aru dan Rokan). Dia mencatat nama raja yang memerintah di Kerajaan Batak adalah Tomyam yang identik dengan nama Tamiang, seperti pernah diberitakan Castanheda juga seorang penjelajah dari Portugis bahwa Raja Tamiang adalah menantu dari Raja Aru
Selanjutnya Duarte Barbosa seorang penulis dan penjelajah dari Portugis pada tahun 1516, mencatat adanya sebuah kerajaan di sebelah selatan pulau Sumatera yang menjadi penghasil utama emas dan di pedalaman lain ada Aru yang berdekatan dengan negara Batta, penduduknya kafir yang gemar makan daging manusia terutama yang mereka bunuh dalam perang. Diteruskan oleh Joao de Barros juga seorang berkebangsaan Portugis pada tahun 1563 kembali menyebut tentang Batak dalam misi penjelajahannya. Dia adalah seorang sejarawan Portugis yang cukup terkemuka. Dalam laporannya dia menyebutkan sebuah penduduk pribumi di bagian pulau yang berlawanan dengan Malaka yang disebut Battas, mereka memakan daging manusia, sangat buas dan merupakan masyarakat yang paling gemar berperang dari seluruh negeri yang pernah dia jelajahi. Demikian juga pada saat Augustin de Beaulieu seorang jenderal Perancis pada tahun 1619-1622 memimpin ekspedisi bersenjata menuju India Timur, dia mengunjungi sejumlah daerah sekitar Aceh dan semenanjung Malaya. Dia menyebut sebuah penduduk pedalaman yang merdeka dan memiliki bahasa yamng berbeda dengan Melayu. Mereka menyembah berhala dan memakan daging manusia, tidak pernah ada tahanan yang ditebus tapi dimakan dengan menggunakan lada dan garam. Namun, Beaulieu tidak secara spesifik menyebut nama penduduk yang dia temui, dia melihat mereka tidak memiliki agama, tetapi sudah mampu mengembangkan konsep pemerintahan dan menguasai beberapa negara. Dari kriteria dan watak penduduk pedalaman yang digambarkan oleh Beaulieu ini jelas mengacu pada suku Batak dan Batak yang dimaksud adalah Simalungun yang pada masa itu dibawah kuasa Raja Marompat.
Informasi tentang Nagur mengemuka kembali dari laporan 2 orang penerjemah Laksamana Cheng Ho (Zheng He), yaitu Ma Huan dan Fei Xin. Armada Cheng Ho yang memimpin sekitar 208 kapal datang mengunjungi Pasai berturut-turut dalam tahun 1405, 1408, dan 1412, pada masa inilah kedua orang penerjemah sekaligus pembantunya merekam keberadaan Nagur yang berada di Aceh. Ma Huan dalam bukunya Yingya Shenglan diterbitkan tahun 1416 menceritakan bahwa Raja Nagur (那孤兒 = Na Ku Erh) dinamakan Raja Muka Bertato, menduduki kawasan sebelah barat Sumentala (Samudera Pasai). Sementara di sebelah barat Nagur berbatas dengan Litai (黎代) dan Lambri (南渤利 = Lan Bo Li), jadi posisi Nagur berada di antara Lidai dan Samudera. Wilayah yang mereka duduki hanya terdiri dari satu desa yang berada di pegunungan, penduduknya merajah wajahnya dengan tiga panah hijau, inilah yang melatarbelakangi munculnya sebutan Raja Muka Bertato. Jumlah penduduknya hanya sekitar seribu keluarga, sistem pertanian yang dikembangkan relatif kecil jika dibandingkan dengan jumlah penduduknya. Jenis tanaman pertanian adalah padi gogo, binatang ternak yang mereka usahakan adalah babi, kambing, unggas, dan bebek. Tidak ada produk yang diekspor karena merupakan negeri yang relatif kecil. Bahasa dan busana yang mereka gunakan sama dengan masyarakat di Samudera Pasai. Dari pemetaan yang dilakukan oleh penulis letak dari Nagur ini berada di sekitar Pirada (Peudada sekarang) masuk Kabupaten Bireuen Aceh sekarang hingga Pidie. Litai, oleh pengelana lain sering juga disebut Lide, barangkali yang dimaksud adalah Lingga yang berada di Aceh Tengah.
Sedangkan menurut hasil dokumentasi Fei Xin yang dimuat dalam bukunya Xingcha Shenglan yang diterbitkan tahun 1436. Nagur merupakan wilayah Negara Muka Bertato (花面國 = Hua Mian Guo) berbatasan dengan Sumatera dan meluas hingga ke Laut Lambri. Wilayah kedudukannya terletak di daerah pegunungan. Di tengah cuaca yang bervariasi, masyarakat Nagur mampu mengolah sawah mereka dengan baik sehingga mampu menghasilkan beras dengan jumlah memadai. Tidak jauh berbeda dengan keterangan Ma Huan di atas, Fei Xin juga mengatakan bahwa para kaum pria memiliki kebiasaan merajah wajah mereka dengan gambar bunga beserta hewan. Rambut mereka yang panjang dibiarkan terurai, bagian atas tubuh dibiarkan terbuka hanya bagian bawah mengenakan sehelai kain. Sementara kaum wanita mengenakan sehelai kain berwarna dan rambut bersanggul di belakang. Binatang yang mereka ternakkan diantaranya sapi, kambing, unggas, dan bebek. Kehidupan mereka berlangsung harmonis, tidak pernah ditemukan ada upaya penindasan dari pihak yang kuat terhadap golongan yang lemah. Antara kaum bangsawan dengan rakyatnya tidak dibatasi jurang pemisah, mereka bersama-sama mengolah lahan demi kemajuan daerah mereka. Tidak ada kesombongan dari golongan orang yang kaya terhadap mereka yang miskin sehingga tindakan kriminal seperti pembunuhan dan pencurian sangat jarang terjadi. Selain memproduksi bahan pangan, tanah subur yang mereka duduki juga ditumbuhi sejumlah tanaman wewangian dan bunga teratai (tunjung biru). Di kawasan pegunungan banyak terdapat belerang, selain itu mereka juga mengembangkan budidaya ulat sutera dan industri tembikar, dan lain sebagainya. Pada saat kunjungan ini, Laksmana Cheng Ho menyerahkan hadiah dari Kaisar China kepada Raja Nagur dan sejak itu pihak Nagur selalu mengirimkan upeti kepada Kaisar China yaitu Lonceng Cakra Donya.
Dalam buku Yingya Shenglan juga diriwayatkan bahwa Raja Samudera Pasai (蘇門答剌 = Su Men Ta La) pernah diserang oleh Raja Nagur dan berhasil terbunuh dengan panah beracun. Karena puteranya masih kecil dan belum sah untuk meneruskan tahta, maka Ratu Su Men Ta La lantas bersumpah membalas dendam kematian suaminya. Ia membuat sayembara yang isinya menyatakan bahwa ia bersedia menikah dan memerintah bersama siapa saja yang sanggup membalaskan dendamnya. Seorang nelayan tua bersedia mengemban tugas tersebut, dengan berani ia memimpin pasukan guna menewaskan raja Nagur. Dengan dibantu prajurit Su Men Ta La, nelayan tua ini berhasil membunuh Raja Nagur, akibatnya pasukan Nagur mundur dan menyerah kalah. Nelayan ini kemudian menikah dengan Ratu Su Men Ta La, keduanya memerintah bersama dengan gelar Raja Tua. Pada tahun 1409, ia berangkat ke China untuk menyerahkan upeti kepada kaisar China dan kembali ke negerinya pada tahun 1412. Putera raja sebelumnya ternyata tidak setuju dengan pengangkatan Raja Tua sebagai pengganti ayahnya, ia lantas bersekongkol dengan para bangsawan guna menghabisi nyawa Raja Tua. Akibat kematian Raja Tua, kemenakannya bernama Su Gan La (蘇幹剌 = Su Gan La) berniat membalas dendam kematian pamannya, ia kemudian mengumpulkan para pengikut dan melarikan diri ke pegunungan. Tidak lama kemudian pada tahun 1415, Cheng Ho pun datang ke tempat ini dan menangkap Su Gan La. Atas bantuan yang diberikan Cheng Ho, putera raja merasa sangat berterima kasih dan sebagai balas jasa ia kemudian terus menerus mengirim upeti ke Tiongkok.
Indikasi tentang eksistensi Nagur mencuat kembali dari catatan Ferdinand Mendez Pinto (1509-1583), barangkali ia orang Eropa pertama yang pernah pergi ke pedalaman utara Sumatra. Dalam karyanya berjudul Peregrination, ia mencatat kunjungan delegasi raja Batak tahun 1539 kepada kapten Melaka yang baru, Pedro de Faria. Ia melaporkan bahwa raja ini penganut paganisme dan ibukotanya bernama Panayu. Ia juga mengisahkan tentang peperangan sengit antara Aceh di masa pemerintahan Raja Ali alias Sultan Alauddin Riayat Shah Al-Qahhar (1537-1569) dengan seorang Raja Batak (Tuan Anggi Sri Timur Raja) dibantu oleh iparnya yang tampil sebagai panglima perang bernama Aquarem Dabolay (Anggaraim Nabolon Saragih Garingging) dari Partuanon Raya. Peperangan ini berlangsung selama dua babak, pada perang pertama dengan mengandalkan ketangguhan panah beracunnya, Nagur berhasil memukul mundur pasukan Aceh dan mengejarnya hingga sampai ke pegunungan yang dinamai Cagerrendan (Cagar Ardan, pen), di sanalah selama 23 hari pasukan Batak mengepung sisa pasukan Aceh yang masih bertahan. Singkat cerita kedua belah pihak sepakat mengadakan perjanjian damai. Namun tidak berselang 2 setengah bulan, Aceh melanggar perjanjian tersebut dan berniat melakukan pembalasan. Adanya bala bantuan 300 orang Turki menjadikan Aceh semakin bersemangat melawan Raja Batak. Pihak Aceh lalu mensiasati strategi bagaimana agar penyerangan mereka tidak menyebar luas dan diketahui Raja Batak. Lantas dibuatlah suatu dalih bahwa Raja Aceh akan berkunjung ke Pasai, tetapi ternyata tidak ke Pasai melainkan menyerang dua buah kampung Batak bernama Jacur dan Lingua. Dalam penyerangan itu, Aceh berhasil menewaskan 3 orang putra Raja Batak dan tujuh ratus orang hulubalang yang merupakan prajurit terbaik sekaligus orang yang dimuliakan di Kerajaan Batak.
