ประวัติศาสตร์ช่วงแรกของอาเจะฮ์ไม่เป็นที่ทราบแน่ชัด โดยมีทฤษฎีหนึ่งกล่าวว่ากำเนิดจากชาวจาม ภาษาอาเจะฮ์เป็นภาษาหนึ่งในกลุ่มภาษาอาเจะฮ์-จาม 10 ภาษา ตามประวัติศาสตร์มลายู กษัตริย์จามปา ซยาห์ เปา กูบะห์ มีโอรสชื่อ ซยาห์ เปาลิง ได้อพยพออกมาเมื่อเมืองวิชายาถูกราชวงศ์เลของเวียดนามตีแตกใน พ.ศ. 2014 และมาก่อตั้งราชอาณาจักรอาเจะฮ์ ผู้ปกครองอาเจะฮ์หันมานับถือศาสนาอิสลามในราวปลายพุทธศตวรรษที่ 21 สุลต่านองค์แรกคืออาลี มูฆายัต ชาห์ ผู้ปกครองสุมาตราเหนือใน พ.ศ. 2063 โดยเข้ายึดครองเดลี เปอดีร ปาไซ และเข้าโจมตีอารู โอรสของพระองค์คือ อะลาอุดดีน อัลกาฮาร์ พยายามขยายอิทธิพลลงไปทางใต้ของสุมาตรา และพยายามข้ามช่องแคบไปยึดครองยะโฮร์และมะละกา อาเจะฮ์ได้รับการสนับสนุนจากจักรวรรดิออตโตมันที่ส่งทหารมาช่วย

ในวันที่ 21 มิถุนายน พ.ศ. 2142 กอร์เนลียึส เฮาต์มัน ชาวดัตช์ได้เดินทางมาถึงอาเจะฮ์และต้องการยึดครองให้เป็นส่วนหนึ่งของอินเดียตะวันออกของเนเธอร์แลนด์ พวกเขาได้รับอนุญาตจากสุลต่านให้เข้ามาซื้อขายพริกไทยได้ ชาวดัตช์เหล่านี้ได้พักอยู่ 3 เดือน ได้ออกซื้อพริกไทยและเครื่องเทศ แต่ถูกชาวพื้นเมืองโจมตีเสียชีวิตไป 68 คน ในปีเดียวกันนั้น ตัวแทนจากบริษัทอินเดียตะวันออกได้เดินทางมาถึงและกลับไปใน พ.ศ. 2145[1][2]

สุลต่านระหว่าง พ.ศ. 2132 – 2147 คือ อาลาอุดดีน เรียยัก ชาห์ อิบน์ ไฟร์มัน ชาห์ ความยุ่งยากภายในทำให้การขยายอำนาจของสุลต่านเป็นไปได้ไม่เต็มที่ จนกระทั่ง อิสกันดาร์ มูดาขึ้นครองราชย์ใน พ.ศ. 2150 เขาขยายอำนาจยึดครองไปทั่วเกาะสุมาตรา และขยายอำนาจเข้าควบคุมปาหังซึ่งเป็นแหล่งผลิตดีบุกในคาบสมุทรมลายา อาเจะฮ์เรืองอำนาจจนถึง พ.ศ. 2172 จึงพ่ายแพ้มะละกาที่ร่วมมือกับโปรตุเกสและยะโฮร์ ซึ่งได้ทำลายกองทัพเรือและทหารราว 19,000 คน ตามบันทึกของโปรตุเกส[3][4] อย่างไรก็ตาม อาเจะฮ์ไม่ได้ถูกทำลายทั้งหมด เพราะยังสามารถไปรุกรานเคดะห์ได้ในปีเดียวกัน และกวาดต้อนพลเมืองมายังอาเจะฮ์ อิสกันดาห์ กานี เจ้าชายจากปาหังซึ่งเป็นพระราชบุตรเขยได้ครองราชย์ต่อมา ในสมัยนี้ อาเจะฮ์ได้เน้นความเป็นเอกภาพทางศาสนาและความเข้มแข็งภายใน เมื่อสิ้นสุดรัชกาลของทานี อาเจะฮ์ปกครองโดยสุลต่านหญิง ในช่วงนี้ อำนาจปกครองของอาเจะฮ์อ่อนแอลง ในขณะที่อำนาจทางศาสนาเพิ่มสูงขึ้น สุลต่านกลายเป็นตำแหน่งเชิงสัญลักษณ์ ดังที่ นักเดินทางชาวเปอร์เซียได้กล่าวถึงสุมาตราเหนือใน พ.ศ. 2223 ว่ามีผู้ปกครองท้องถิ่นแยกกันปกครองเป็นอิสระ