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

เมืองสิงหนครแรกตั้งเมื่อ พ.ศ. 1899 สมัยสมเด็จพระรามาธิบดีที่ 1 รายนามเจ้าเมืองในช่วงต้นนั้นไม่ปรากฏ ปรากฏรายนามเจ้าเมืองตั้งแต่ พ.ศ. 2146 เป็นต้นไป คือ

1. ตวนกูดะโต๊ะ โมกอลล์ 2146-2163
2. สุลต่านสุไลมาน ชาห์ รามาธิบดี 2163-2212
3. สุลต่านมุสตาฟา 2212-2223

ตั้งแต่ พ.ศ. 2223 เป็นต้นไป เมืองสงขลากลายเป็นเมืองร้าง

หลักฐานของไทยและต่างชาติต่างระบุว่า เจ้าเมืองสงขลาหัวเขาแดงเป็นมุสลิม ในพงศาวดารเมืองสงขลากล่าวว่า สุลต่านสุไลมานเป็นแขกชาวชวาจากเมืองลาไสย เกาะสุมาตรา บันทึกของชาวดัตช์ปี พ.ศ. 2162 เรียกว่าโมกุล และบันทึกของพ่อค้าชาวอังกฤษได้บอกว่า ดะโต๊ะ โมกอลล์ เมืองสงขลาตามแผนกัลปนาวัดต่าง ๆ ขึ้นวัดพะโคะนั้น โมกอลล์เข้ายึดครอง ปรากฏข้อเท็จจริงในแผนผังว่าเป็นชุมชนท่าเรือที่มีคนอาศัยอยู่ก่อนแล้ว มีป้อมปืนตั้งอยู่บนบริเวณใกล้เคียงเมืองสงขลา ก็บ้านของราษฎรอาศัยอยู่อย่างหนาแน่น

ตั้งแต่พุทธศตวรรษที่ 18-23 ที่เมืองนครศรีธรรมราชเปลี่ยนฐานะจากเมืองพระยามหานครของกรุงสุโขทัยไปสู่ฐานะหัวเมืองของรัฐบาลกลางกรุงศรีอยุธยาที่พยายามขยายพระราชอาณาเขตไปโดยการลดอำนาจบทบาทและอิทธิพลในตอนปลายพุทธศตวรรษที่ 20 เมืองนครศรีธรรมราชถูกแบ่งออกเป็นตัวเมืองย่อย 4 เมืองคือ นครศรีธรรมราชเป็นเมืองเอก มีเมืองไชยา เมืองชุมพร และเมืองพัทลุงเป็นเมืองตรี สภาพเช่นนี้ทำให้ศูนย์อำนาจท้องถิ่นในภาคใต้ (เช่น เมืองนครศรีธรรมราช) ถูกแบ่งออกเป็นเสี่ยง ๆ และอ่อนแอ จึงเป็นโอกาสให้ดะโต๊ะ โมกอลล์ ก่อตั้งเมืองสงขลาของกลางพุทธศตวรรษที่ 22 ตามสภาพภูมิศาสตร์เมืองสงขลาขึ้นอยู่กับพัทลุงแต่ในระยะดังกล่าวเมืองพัทลุงตกใต้อิทธิพลเมืองนครศรีธรรมราช มีหน้าที่ดูแลเมืองสงขลาด้วยในฐานะที่เป็นหัวเมืองถวายดอกไม้เงิน ดอกไม้ทอง และเครื่องราชบรรณาการต่อกรุงศรีอยุธยา

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

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

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

ประจวบกับในปี พ.ศ. 2171 สมเด็จพระเจ้าทรงธรรมเสด็จสวรรคต เกิดความไม่สงบขึ้นในราชสำนักกรุงศรีอยุธยา เมื่อพระยากลาโหมสุริยวงศ์ได้รับสถาปนาขึ้นครองราชย์สมบัติทรงพระนามว่า สมเด็จพระเจ้าปราสาททอง เมืองสงขลาจึงถือโอกาสปลดแอกจากไทย ปี พ.ศ. 2158 กองทัพกรุงศรีอยุธยาได้ยกกองทัพมาปราบ แต่ขาดกำลังสนับสนุนจากไพร่พลท้องถิ่นโดยเฉพาะจากนครศรีธรรมราช และป้อมปราการแข็งแกร่งเกินกำลังจะปราบลงได้

พระเจ้าเมืองสงขลาสามารถตั้งตัวเป็นอิสระเป็นเวลาถึง 26 ปีตลอดสมัยพระเจ้าปราสาททอง หลังจากเจ้าเมืองสงขลาองค์แรกสิ้นพระชนม์ในปี พ.ศ. 2211 มุสตาฟาโอรสก็ตั้งตนขึ้นเป็นพระเจ้าเมืองสงขลาองค์ที่สอง เป็นช่วงของการขยายอำนาจของเมืองสงขลาไปยังหัวเมืองใกล้เคียง โดยเฉพาะเมืองพัทลุง ปัตตานี และนครศรีธรรมราช

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

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

ส่วนร่องรอยของการเข้ามาพำนักที่สงขลามีหลักฐานในปัจจุบันคือ ที่ฝังศพของพวกดัตช์ 22 สุสาน ซึ่งอยู่ห่างจากเมืองสงขลาริมทางถนนสงขลา-ระโนดที่หัวเขาแดงไปทางทิศเหนือประมาณ 1,700 เมตร อยู่ใกล้กับที่ฝังศพสุสานสุลต่านสุไลมาน ชาวบ้านเรียกว่าทวดหุมหรือมะระหุมตั้งอยู่ในตำบลหัวเขา ที่ฝังศพมีศาลาคร่อมก่อด้วยอิฐไม่มีฝาผนัง หลังคาทรงปั้นหยา มุงกระเบื้องดินเผา เป็นที่เคารพของชาวบ้านหัวเขา และเชื่อกันว่าลูกหลานมะระหุ่มคือต้นตระกูลของสกุล ณ พัทลุง ซึ่งไปมีอำนาจเป็นเจ้าเมืองพัทลุงในช่วงหลัง

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