assalamua'laikum everything ..
The land of East Aceh has been inhabited by humans since the Middle Stone Age (Mesolithic Age). This is based on the results of research conducted by DR. H. Kupper who mentioned that has been found tool made from rubbing stone used by the human being on the excavation area between Kuta Binjai and Alue Ie Mirah ± 15 Km from City Idi.
The Young Stone Age (Neolithic) in Southeast Asia is estimated to be about 1,000 years before Christ. At that time appeared Proto Malay Nation (Old Malay) which spread to various parts including Aceh Timur and Aceh Utara. Their culture is more advanced than the previous nation, they have cooked food and cultivated.
Then about 300 years before the emergence of the Deutoro Malay Nation (New Malay) with a more advanced culture. Their arrival in Aceh made some of Proto Malay (Old Malay) who did not want to assassilate to the hinterland. According to historians the remains of Proto Malay Nation is the ancestors of Gayo, Batak, Nias and Toraja. 
When sea travel has advanced rapidly, there are also coming to Aceh Parsia merchants, Gujarat (India), China and Europe to trade and look for Peureulak Tree trees to serve as ships. After the Islamic religion developed in the Arabian peninsula also sent the preachers to the east to spread the religion of Islam. They landed in Peureulak and settled there. 
On Tuesday 1 Muharram 225 H (840 AD) was proclaimed the standing of the Peureulak Islamic Empire with the crowning of Sayed Maulana Abdul Aziz Shah (840-864M) as the first king, with the royal capital named Bandar Khalifah. Ibn Bathuthah and Marcopolo had visited Peureulak and wrote in his account that the country had advanced rapidly under the reign of a religious king. Society has embraced Islam although there are still animist and very primitive.
