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

เนื่องจากตั้งอยู่ใกล้ที่ทำการศาลากลางจังหวัดยะลาและใกล้ที่ทำการ อำเภอเมืองยะลา ซึ่งเป็นบริเวณที่เรียกกันว่า "ตลาดนิบง"

ในปี พ.ศ.2501 คณะผู้บริหารได้กู้เงินจากกองทุนส่งเสริมกิจการเทศบาล เป็นเงิน 1,200,000 บาท เมื่อวันที่ 10 มีนาคม พ.ศ.2501 จัดสร้าง อาคารสำนักงานเทศบาลถาวรขึ้นเป็นอาคารตึก 2 ชั้น ขนาดใหญ่แบบ พิเศษของกรมโยธา เทศบาล เป็นเงิน 1,174,921 บาท สร้างเสร็จเมื่อวันที่ 1 มิถุนายน พ.ศ. 2502 ได้ประกอบพิธีเปิดอาคาร เมื่อวันที่ 24 มิถุนายน พ.ศ. 2502 ทั้งได้ย้ายสำนักงานจากอาคารเรียน มาสู่อาคารหลังใหม่ ซึ่งเป็นอาคารหลังหน้าสุดที่ใช้อยู่ใน สำนักงาน เทศบาลปัจจุบัน และได้มีการขยายปรับปรุงอาคารให้เหมาะสมกับสภาวะ ที่เป็นอยู่ทุกวันนี้

เทศบาลเมืองยะลาได้รับการยกฐานะเป็นเทศบาลนครยะลา ตามประกาศในราชกิจจานุเบกษา ฉบับกฤษฎีกา เล่มที่ 112 ตอนที่ 40 ก ลงวันที่ 24 กันยายน พ.ศ. 2538 ยกฐานะเทศบาลเมืองยะลาเป็น เทศบาลนครยะลา โดยมีผลบังคับ ใช้ตั้งแต่วันที่ 25 กันยายน พ.ศ. 2538 เป็นต้นไป