สุไหงโก-ลกเดิมเป็นป่าดงดิบรกร้างว่างเปล่าในเขตตำบลปูโยะ อำเภอสุไหงปาดี ความเป็นป่าทึบทำให้ชาวบ้านเรียกว่า "ป่าจันตุหลี" หมายความว่า ทึบจนเรียกไม่ได้ยิน เหมือนหูหนวก เมื่อเริ่มมีผู้เข้ามาหักร้างถางพง จากชื่อป่าจันตุหลีเปลี่ยนเป็น "สุไหงโก-ลก" ซึ่งเป็นภาษามลายู มาจากคำว่า "สุไหง" แปลว่า แม่น้ำ ลำคลอง และคำว่า "โก-ลก" แปลว่า คดเคี้ยว ถ้าเป็นคำนามหมายถึง มีดพร้า (ที่คนพื้นเมืองนิยมใช้) เมื่อนำคำว่าสุไหงรวมกับโก-ลก จึงหมายถึง แม่น้ำที่คดเคี้ยว หรือ แม่น้ำมีดอีโต้ ชาวบ้านคงเรียกชื่อเมืองตามแม่น้ำที่ไหลผ่านพื้นที่ ปัจจุบันแม่น้ำสายนี้เป็นเส้นกั้นพรมแดนประเทศไทยกับรัฐกลันตัน ประเทศมาเลเซีย

เมื่อปี พ.ศ. 2460 ได้มีการกรุยทางเพื่อก่อสร้างทางรถไฟเชื่อมไปรัฐกลันตันโดยกำหนดตั้งสถานีรถไฟในเขตป่าจันตุหลี ซึ่งต่อมาก็คือสถานีรถไฟสุไหงโก-ลก ซึ่งเป็นสถานีรถไฟสถานีสุดท้ายของประเทศไทยที่มีระยะทางไกลที่สุด ชาวบ้านปูโยะที่เห็นการณ์ไกลได้เริ่มเข้ามาจับจองที่ดิน บ้างก็ขออนุญาตทำสวนยางพาราแต่ยังไม่มีการปลูกสร้างบ้านเรือน ชุมชนที่ชาวปูโยะติดต่อค้าขายมีเฉพาะรันตูปันยังของกลันตันซึ่งมีราษฎรอยู่อาศัยและประกอบอาชีพค้าขายเป็นหลักแหล่งแล้ว

แม้ว่าจะเปิดการเดินรถไฟเป็นรถรวมจากหาดใหญ่ไปสิ้นระยะที่สุไหงโกลกเมื่อวันที่ 17 กันยายน พ.ศ. 2464 แต่ราษฎรก็ยังไม่ได้รับความสะดวก เนื่องจากป่าถูกจับจองไว้โดยมิได้ก่อประโยชน์ ดังนั้น ในปี พ.ศ. 2468 นายวงศ์ ไชยสุวรรณ อาศัยที่ดินของนายฉ่ำที่หลังสถานีรถไฟ พร้อมนายฮวด นายซั้ว นายกวาซ่อง นายเจ๊ะหมัด นายหลีหลง และนายหวัง รวม 7 คน เป็นเพื่อนบ้านใกล้เรือนเคียงซึ่งมีทั้งคนไทย คนมุสลิม และคนจีนร่วมกันพัฒนาเมือง (สุนทรธรรมพาที: 2501) นับเป็นต้นแบบแห่งสังคมพหุลักษณ์ที่มีเสน่ห์ยิ่ง ปี พ.ศ. 2472 กำนันตำบลปูโยะถึงแก่กรรม นายวงศ์ ไชยสุวรรณจึงได้รับแต่งตั้งเป็นกำนันได้พัฒนาจนเริ่มกลายเป็นเมือง ได้อาศัยเงินจากเพื่อน 5 คน ได้ 500 บาท ตัดถนนถึง 31 สาย ลักษณะถนนตัดพาดผ่านกันเป็นตาหมากรุก จึงมีสี่แยกจำนวนมาก แต่เชื่อว่านั่นคือแนวคิดการป้องกันการลุกลามของไฟเมื่อเกิดอัคคีภัย ดังนั้นจึงมีผู้คนอพยพเข้ามาตั้งถิ่นฐานและประกอบอาชีพมากมาย ตำบลปูโยะมีประชากรถึง 12,300 คน ทางราชการจึงแยกเป็น 2 ตำบล คือ ตำบลปูโยะและตำบลสุไหงโก-ลก

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

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

หลังจากตั้งเทศบาลแล้ว 7 ปี ตำบลสุไหงโก-ลกจึงได้ยกฐานะเป็น กิ่งอำเภอสุไหงโก-ลก[1] ขึ้นกับอำเภอสุไหงปาดี โดยมีเขตปกครอง 4 ตำบล คือ ตำบลสุไหงโก-ลก ตำบลปูโยะ ตำบลปาเสมัส ของอำเภอสุไหงปาดี และตำบลมูโนะ (รับโอนมาจากอำเภอตากใบ) ตามประกาศกระทรวงมหาดไทยลงวันที่ 18 พฤศจิกายน พ.ศ. 2490 โดยให้มีผลตั้งแต่วันที่ 9 ธันวาคม ปีเดียวกัน

กระทั่งวันที่ 1 มกราคม พ.ศ. 2496 กิ่งอำเภอสุไหงโก-ลก อำเภอสุไหงปาดี จังหวัดนราธิวาส จึงได้รับการยกฐานะเป็น อำเภอสุไหงโก-ลก[2] ตามประกาศกระทรวงมหาดไทยลงวันที่ 23 กุมภาพันธ์ พ.ศ. 2496 โดยให้มีผลตั้งแต่วันที่ 10 มีนาคม ปีเดียวกัน มีนายนอบ นพสงศ์ เป็นนายอำเภอคนแรก เขตการปกครอง 4 ตำบลเท่าเดิม

ส่วนตำบลสุไหงโก-ลกอยู่ในเขตเทศบาล ความน่าภูมิใจของเทศบาลนี้คือ เป็นเทศบาลเดียวในประเทศไทยที่จัดตั้งก่อนอำเภอถึง 13 ปีและเกิดจากความต้องการของประชาชน ปัจจุบันเทศบาลตำบลสุไหงโก-ลกได้รับการยกฐานะเป็นเทศบาลเมืองสุไหงโก-ลกเมื่อ ปี พ.ศ. 2545 เป็นต้นมา ปัจจุบันอำเภอสุไหงโก-ลกมีความเจริญและเป็นศูนย์กลางทางเศรษฐกิจของภาคใต้ตอนล่าง มีด่านการค้าชายแดนที่ใหญ่ที่สุดของฝั่งตะวันออก เป็นศูนย์กลางของการค้าขายส่งสินค้าทั้งพืชผักผลไม้ ตลอดจนไม้ สินค้าอิเล็กทรอนิกส์ เครื่องใช้ไฟฟ้า และขนมนมเนยจากประเทศเพื่อนบ้าน และเป็นศูนย์กลางทางการท่องเที่ยวของนักท่องเที่ยวจากประเทศมาเลเซีย สิงคโปร์ และอินโดนีเซีย ที่ผ่านเข้าออกด่านสุไหงโก-ลกกว่าปีละหลายแสนคน