เทศบาลเมืองสกลนคร ได้รับการจัดตั้งขึ้นเมื่อวันที่ 11 มีนาคม พ.ศ. 2479 ตามพระราชกฤษฎีกาจัดตั้งเทศบาลเมืองสกลนคร จังหวัดสกลนคร พ.ศ. 2479 (ประกาศใน ราชกิจจานุเบกษา เล่มที่ 53 หน้า 1319 ลงวันที่ 14 มีนาคม พ.ศ. 2479)[2] นายกเทศมนตรีคนแรก คือ ขุนถิรมัยสิทธิการ เข้าดำรงตำแหน่ง เมื่อวันที่ 15 กันยายน พ.ศ. 2480 มีพื้นที่ 13 ตารางกิโลเมตร โดยยกเอาพื้นที่ตำบลธาตุเชิงชุมทั้งตำบลเป็นเขตเทศบาล สำนักงานเทศบาลแต่ก่อนเรียกว่า "ศาลาเทศบาลเมืองสกลนคร" เดิมนั้นตั้งอยู่สถานีรถปรับอากาศ ปัจจุบันสถานที่ตั้งเข้าที่ดินของวัดแจ้งแสงอรุณ เมื่อก่อนนั้นเป็นที่ตั้งของตลาดสดเทศบาล ต่อมาเมื่อปี พ.ศ. 2500 จึงย้ายมาตั้งสำนักงานมาอยู่ในสถานที่ปัจจุบัน

ในปี พ.ศ. 2533 ได้มีการขยายเขตเทศบาลออกไปครอบคลุมท้องที่ข้างเคียง[3] ได้แก่ บางส่วนของตำบลงิ้วด่อน ตำบลห้วยยาง ตำบลดงมะไฟ ตำบลธาตุนาเวง และตำบลฮางโฮง ทำให้มีพื้นที่เพิ่มขึ้นเป็น 54.54 ตารางกิโลเมตร จนกระทั่งได้รับการยกฐานะจากเทศบาลเมืองสกลนครเป็น เทศบาลนครสกลนคร ตามประกาศกระทรวงมหาดไทยลงวันที่ 24 มกราคม พ.ศ. 2555 ซึ่งมีผลตั้งแต่วันที่ 8 มีนาคม ปีเดียวกัน[4]