คำว่ากรือเซะ เพี้ยนมาจากคำว่า กรือเซะห์ เป็นภาษามลายู มีความหมายว่า สะอาดบริสุทธิ์ เมืองกรือเซะที่มีเจ้าเมืองมาปกครอง ได้ก่อกำเนิดขึ้นในช่วงสมัยการปกครองของพระยาอินทิรา โดยคำบอกเล่าของนายมาหามุ สาและ อายุ 50 ปี พนักงานดูแลโบราณสถาน และนายอาฮามะ ฮะซา อายุ 34 ปี เจ้าหน้าที่โบราณสถาน ว่าในสมัยช่วงปลายของศูนย์กลางที่ตั้งเมืองลังกาสุกะนั้น ซึ่งมีเมืองหลวงของลังกาสุกะ ชื่อ โกตามะห์ลิฆัย (ปัจจุบันคือเมืองยะรัง) พระยาอินทิรา ที่ปกครองเมืองในสมัยนั้นมีความคิดที่จะย้ายที่ตั้งของเมืองลังกาสุกะ เนื่องจากการคมนาคมทางการค้าที่ไม่ค่อยสะดวกในการเข้าถึงเมืองยะรัง ซึ่งเรือใหญ่ไม่สามารถผ่านคลองที่รองรับการสัญจรของเรือขนาดเล็กเท่านั้น แต่ยังไม่รู้ว่าจะย้ายไปแห่งใด พระยาอินทิราได้ยินคำร่ำลือว่ามีประชาชนชื่อ โต๊ะกาซอ ได้ชักชวนชาวเมืองย้ายไปตั้งรกรากไปยังแถบชายหาด โดยได้บอกกับชาวเมืองว่าแถบชายหาดมีความเจริญสมบูรณ์ทางด้านธรรมชาติ และการค้าขาย มีพ่อค้าจากหลากหลายประเทศเข้ามาทำการค้าขาย พระยาอินทิราได้ยินดังนั้น จึงเกิดความไม่พอใจต่อโต๊ะกาซอเป็นอย่างมาก ที่ได้ชักชวนชาวเมืองย้ายออกไปจากถิ่นฐานเดิม จึงได้สั่งให้ประหารโต๊ะกอซอ แต่หลังจากนั้นไม่นาน พระยาอินทิราก็ได้ย้ายไปอยู่ยังสถานที่ดังกล่าวตามคำบอกเล่าของโต๊ะกาซอ ประกอบกับพระยาอินทิราชอบการล่าสัตว์ จึงได้ออกไปล่าสัตว์ ณ หมู่บ้านเปาะตานี ได้พบกับกระจงขาวตัวหนึ่ง แต่กระจงขาวได้วิ่งหนีหายบริเวณชายหาด จึงได้สั่งให้ทหารออกตามหากระจงขาวดังกล่าว พระยาอินทิราได้สอบถามทหารว่าพบกระจงขาวหรือไม่ ทหารจึงตอบไปว่า Helae di Panta ni ซึ่งในสมัยนั้นจะใช้ภาษามลายูในการสื่อสาร แปลว่า กระจงขาวได้หายที่ชายหาดนี้ พระยาอินทิราจึงได้เดินทางไปดูยังสถานที่ๆ กระจงขาวหายตัวไป พระยาอินทิราจึงได้พบกับหาดทรายขาว จึงเป็นที่มาของชื่อเมืองกรือเซะห์ หรือกรือเซะในปัจจุบัน ทำให้พระยาอินทิราตัดสินใจย้ายเมืองลังกาสุกะจากยะรัง มายังกรือเซะห์ และได้สร้างเมืองกรือเซะห์ ให้มีความเจริญรุ่งเรืองทางด้านการค้า เป็นแหล่งค้าขายของชาวต่างชาติ เช่น จีน อินเดีย ฮอลันดา และกลุ่มชาติตะวันออกกลาง อย่างเปอร์เซีย