เกอดะฮ์เป็นนครรัฐที่มีประวัติศาสตร์อันยาวนาน จากหลักฐานที่ยังหลงเหลืออยู่บริเวณหุบเขาบูจัง ซึ่งเป็นร่องรอยการตั้งอยู่ของอาณาจักรฮินดู-พุทธ ในสมัยศตวรรษที่ 4 อาณาจักรแห่งนี้ถือว่าเป็นอารยธรรมที่เก่ามากบนพื้นแผ่นดินมาเลเชีย และมีการสืบเชื้อสายปกครองดินแดนในแถบนี้เรื่อยมาจนถึงสมัยของ กษัตริย์ชื่อ มะโรง มหาวงศ์ ซึ่งพระองค์นับถือศาสนาฮินดู โดยราชวงศ์ของพระองค์ ปกครองเกอดะฮ์เรื่อยมาจนถึงกษัตริย์องค์ที่ 9 พระองค์มหาวงศ์ เกอดะฮ์มีการติดต่อค้าขายกับอาหรับจนรับเอาอารยธรรมและศาสนาของชาวอาหรับเข้ามายึดถือ พระองค์มหาวงศ์ หันมานับถือศาสนาอิสลาม และเปลี่ยนชื่อเป็น สุลต่าน มุสซาฟา ชาห์ ในปี พ.ศ. 1679 (ค.ศ. 1136)

ตามประวัติศาสตร์แต่โบราณมา เมืองเกอดะฮ์ถูกเรียกว่าเมืองไทรบุรีมาโดยตลอด โดยในศตวรรษที่ 7-8 เมืองไทรบุรีขึ้นอยู่กับอาณาจักรศรีวิชัย หลังอาณาจักรศรีวิชัยล่มสลาย และเกิดอาณาจักรมะละกา ทางตอนใต้ เมืองไทรบุรีจึงไปขึ้นอยู่กับมะละกา จนกระทั่งศตวรรษที่ 17 พวกอาเจะฮ์ก็เข้าเข้าโจมตีเมืองไทรบุรี เจ้าเมืองไทรบุรีจึงได้ขอความช่วยเหลือยังอาณาจักรอยุธยาและถ้าปลดปล่อยสำเร็จจะขอเป็นเมืองประเทศราชของอาณาจักรอโยธยา โดยทางอาณาจักรอโยธยาได้ส่งกำลังทหารเข้ามาปลดปล่อยเมืองไทรบุรีจากพวกอาเจะฮ์เป็นผลสำเร็จ ซึ่งตั้งแต่นั้นเมืองไทรบุรี ศตวรรษที่ 18 ก็อยู่ภายใต้อำนาจของอาณาจักรอโยธยาต่อมาถึงอาณาจักรสยามมาโดยตลอด ในสมัยพระบาทสมเด็จพระจุลจอมเกล้าเจ้าอยู่หัว ราชอาณาจักรสยามได้มีการปรับปรุงการดูแลหัวเมืองทางใต้ใหม่ โดยตั้งรูปแบบมณฑลขึ้นและเปลี่ยนการเรียกเมืองเป็นจังหวัด จึงทำให้เมืองไทรบุรีเปลี่ยนชื่อเป็นจังหวัดไทรบุรีสังกัดมณฑลมาลัย

ต่อมาอังกฤษได้เข้ามามีอิทธิพลเหนือดินแดนมลายูทางใต้ของเมืองไทรบุรี ในสมัยพระบาทสมเด็จพระพุทธยอดฟ้าจุฬาโลก อังกฤษเข้ามามีอำนาจในดินแดนมลายู โดยเจ้าเมืองไทรบุรีมีแผนการหวังที่จะให้อังกฤษโดยมีข้อแม้ว่าต้องช่วยเมืองไทรบุรีให้ปลดปล่อยออกอำนาจของสยาม โดยเจ้าเมืองไทรบุรีมีข้อแลกเปลี่ยนคือยกเกาะหมากหรือเกาะปีนังในปัจจุบัน ให้กับอังกฤษ แต่อังกฤษสนใจเฉพาะการค้าเท่านั้นไม่มีต้องการมีเรื่องกับสยามเพราะการค้าของอังกฤษในสยามกำลังเป็นไปได้ด้วยดี จึงปฏิเสธเจ้าเมืองไทรบุรีไปโดยให้เหตุผลว่าไม่ต้องการยุ่งเกี่ยวกับเรื่องภายในของประเทศอื่น ปีนังจึงอยู่ในการปกครองของต่อไป

ต่อมาอังกฤษยึดอินเดียและพม่าเป็นรัฐอารักขาได้แล้ว และมีแผนขยายอำนาจอังกฤษจึงยอมรับข้อตกลงรับเกาะหมากหรือเกาะปีนังจากเมืองไทรบุรี โดยเรื่องนี้เมืองไทรบุรีไม่ได้แจ้งให้สยามซึ่งมีอำนาจเหนือเมืองไทรบุรีในขณะนั้นทราบ ทางสยามเมื่อทราบจึงส่งกองทัพยกกำลังเพื่อมาจับเจ้าเมืองไทรบุรีเพื่อพิจารณาโทษที่กรุงเทพฯ แต่ปรากฏว่าเจ้าเมืองไทรบุรีหนีเข้าไปอยู่ในเขตของอังกฤษ โดยสยามในขณะนั้นมีนโยบายไม่อยากเป็นศัตรูและรู้ว่าไม่สามารถทัดทานอำนาจของอังกฤษได้ ซึ่งผลทำให้เกาะปีนังตกเป็นของอังกฤษตั้งแต่ 11 สิงหาคม พ.ศ. 2329 ต่อมาในสมัยพระบาทสมเด็จพระจุลจอมเกล้าเจ้าอยู่หัว ไทยต้องการยกเลิกสิทธิสภาพนอกอาณาเขตที่ได้เคยทำไว้กับอังกฤษโดยต้องการให้ได้มาซึ่งอำนาจ ศาลไทยที่จะพิจาณาคดีและบังคับคดีความผิดของคนอังกฤษและคนในบังคับอังกฤษซึ่งขณะนั้นได้สร้างปัญหามากมายกับสยาม โดยอังกฤษมีข้อแลกเปลี่ยนคือสยามจะต้องยกสี่รัฐมาลัยให้เป็นของอังกฤษ ประกอบด้วยกลันตัน, ตรังกานู, ไทรบุรี, ปลิศ ซึ่งสยามได้พิจารณาและตัดสินใจยอมยกสี่รัฐมาลัยให้แก่อังกฤษเมื่อ 10 มีนาคม 2451 (นับศักราชใหม่ต้องเป็นปี 2452 เพราะเดิมทีไทยนับศักราชใหม่ตั้งแต่เดือนเมษายน ไปสิ้นสุดที่เดือนมีนาคม ในศักราชถัดไปของปฏิทินสากล) เพื่อแลกเปลี่ยนตามเงื่อนไข ด้วยเหตุนี้เมืองไทรบุรีก็ตกอยู่ภายใต้รัฐมลายูของอังกฤษ เมื่อเมืองไทรบุรีได้เข้าไปรวมอยู่รัฐมลายูของอังกฤษซึ่งประชาชนส่วนใหญ่นับถือศาสนาอิสลาม จึงได้เปลี่ยนชื่อไทรบุรีเป็นเกอดะฮ์ตั้งแต่บัดนั้นเป็นต้นมา