เมืองสกลนครตั้งอยู่ริมหนองหานใหญ่ กว้างและเป็นแหล่งเพาะพันธุ์ปลาน้ำจืด นับเป็นจังหวัดเดียวในภาคอีสานที่อุดมด้วยน้ำ เป็นที่ตั้งอยู่บนที่สูง สูงกว่าระดับน้ำทะเล 172 เมตร มีเทือกเขาภูพานเป็นเทือกเขาสำคัญของจังหวัด ตอนกลางของจังหวัดเป็นที่ราบต่ำเหมาะแก่การทำนา โดยเฉพาะบริเวณหนองหาน
เมืองเดิม อยู่ที่ริมหนองหาน ตรงท่านางอาบน้ำ (ปัจจุบันเป็นเขตบ้านท่าศาลา ตำบลนาแก้ว อำเภอโพนนาแก้ว)
ตำนานเมืองสกลนคร เมืองสกลนครมีชื่อปรากฏอยู่ในตำนานสืบเนื่องมาจนปัจจุบันหลายชื่อด้วยกัน คือ เมืองสุวรรณภิงคาร เมืองสกลทวาปี และเมืองสกลนครตามเรื่องสืบเนื่องจากท้าวผาแดงนางไอ่คำว่าพญานาคได้มาสร้างเมืองสุวรรณภิงคาร อยู่ริมหนองหานหลวง พญาสุวรรณภิงคารได้ดาเมืองอินทปัฐนครเป็นมเหสี นามว่า จรวยเจงเวง ทั้งสองเลื่อมใสพระพุทธศาสนา ได้เข้าเฝ้าพระพุทธเจ้าซึ่งประทับรอยพระบาทไว้ให้เป็นที่สักการะ และได้ก่ออุบมุงสวมรอยพระบาทไว้ ภายหลังคือพระธาตุเชิงชุม ต่อมาเมืองสุวรรณภิงคารรกร้างว่างเปล่าไร้ผู้ปกครอง สมัยกรุงธนบุรี เจ้าพระยาจักรี (พระบาทสมเด็จพระพุทธยอดฟ้าจุฬาดลกมหาราช) ยกทัพมาทางนี้ก็ให้ประฏิสังขรณ์ตั้งขึ้นเป็นบ้านเมือง ให้พระอุปฮาด เมืองกาฬสินธุ์ยกไพร่พลมาตั้งเป็นเมืองรอบพระธาตุเชิงชุม ให้ชื่อว่าเมืองสกลทวาปี สมัยรัชกาลที่ 3 เมื่อเจ้าพระยาราชสุภาวดียกทัพมาปราบเจ้าอนุวงศ์เวียงจันทน์ได้ทำเมืองนี้ให้ร้าง และนำไพร่พลไปอยู่เมืองกระบิลบุรี เมืองประจันภายหลังใน พ.ศ. 2372 ทรงโปรดเกล้าให้อุปฮาดคำสาย และราชวงศ์คำเมืองมหาชัยพาไพร่พลไปอยู่สกลทวาปี ตั้งเมืองขึ้นใหม่ หลังจากนั้นจึงเปลี่ยนชื่อเมืองเป็นสกลนคร
สกลนครเป็นเมืองเก่าเมืองหนึ่งในสมัยขอมเรืองอำนาจ เป็นเมืองเสบียงสะสมอาวุธ เดิมชื่อเมืองหนองหานหลวง ขุนขอมราชบุตรเจ้าเมืองอินทปัทม์นครได้สร้างขึ้น แต่ประวัติอีกแห่งหนึ่งกล่าวว่า ในสมัยอดีตมีนิทานซึ่งสมเด็จพระสัมมาสัมพุทธเจ้าทรงพระนามว่า โคดม ได้ทรงตรัสไว้ในอุรังคนิทานหรือตำนานพระธาตุพนมว่า พระยาอินทปัทม์นคร เป็นหัวหน้ามาจากเขมร ได้พาครอบครัวบ่าวไพร่ มาสร้างเมืองขึ้นที่ริมหนองหานตรงท่านางอาบ (ขณะนี้อยู่ที่ท่าศาลา ตำบลนาแก้ว อำเภอโพนนาแก้ว) ขุนขอมได้เป็นเจ้าเมืองต่อๆ กันมาจนถึงเจ้าผู้ครองเมืองชื่อว่า "พระยาสุวรรณภิงคาร" มีชายาชื่อว่า "นางนารายณ์เจงเวง"
ต่อมาเมืองหนองหานหลวงเกิดแห้งแล่ง การทำนาและการทำมาหากินของราษฎรอัตคัด พวกเจ้าเมืองเขมรที่ปกครองอยู่จึงอพยพกลับ เมืองหนองหานหลวงจึงเป็นเมืองร้าง แต่จะร้างเมื่อใดไม่ปรากฏ สันนิษฐานว่าคงจะร้างในคราบที่ขอมเสื่อมอำนาจลง
ตามตำนานพระธาตุพนมกล่าวว่า เมื่อสิ้นบุญพระยาสุวรรณภิงคารแล้ว เมืองหนองหานหลวงถูกน้ำท่วม ผู้คนหนีน้ำอพยพไปอยู่ที่เวียงจันทน์พวกหนึ่ง และอพยพไปอยู่เมืองสาเกตนคร (เมืองร้อยเอ็ด) พวกหนึ่ง เมืองหนองหานหลวงร้างมาจนถึงสมัยไทยเข้าครอบครอง ซึ่งในหนังสือพงศาวดารเมืองสกลนคร ได้กล่าวไว้ว่าเมืองสกลนครนั้นมีผู้ครองเมืองปกครองต่อๆ กันมาถึง 3 ตอน หรือ 3 วงศ์ คือ
ตอนที่ 1 แยกวงศ์ตระกูลมาจากเมืองอินทปัทม์นคร
ตอนที่ 2 แยกวงศ์ตระกูลมาจากเมืองกาฬสินธุ์
ตอนที่ 3 แยกวงศ์ตระกูลมาจากเมืองนครพนม
ตอนที่ 1 แยกวงศ์ตระกูลมาจากกรุงอินท์ปัทม์นคร
ตำนานกล่าวว่า ในสมัยพระพุทธเจ้ากัสสป นั้น พระเจ้าอินทปัทม์นคร ได้แต่งตั้งให้ขุนขอม ราชนัดดา ยกพลมาตั้งเมืองขึ้นที่ฝั่งหนองหานหลวง ตรงท่านางอาบ ให้ชื่อว่า "เมืองหนองหานหลวง" ขึ้นกับกรุงอินทปัทม์
ต่อมาขุนขอมสิ้นพระชนม์ "เจ้าสุรอุทกกุมาร" ราชโอรสได้เป็นพระยาครองเมืองแทน วันหนึ่งได้เสด็จตรวจเขตแดนถึงปากแม่น้ำมูล ทราบว่าพระเจ้าอินทปัทม์นครผู้เป็นพระอัยกาและขุนขอมผู้เป็นพระบิดาได้มอบให้ "ชนะมูลนาค" เป็นผู้รักษา พระองค์ทรงขัดเคืองว่าพระอัยกาและพระบิดาไม่สมควรมอบให้สัตว์เดรัจฉานรักษาเขต จึงได้แสดงฤทธิ์ต่อสู้กับพญานาค จนสิ้นกำลังทั้งสองฝ่าย
เมื่อพระเจ้าสุรอุทกเสด็จกลับเมืองหนองหานหลวงแล้ว พญานาคซึ่งผูกพยาบาทอยู่ได้ติดตามมาจนถึงเมืองหนองหานหลวงแล้วจำแลงกายเป็นฟานเผือก (อีเก้งเผือก) เดินผ่านเมือง พระเจ้าสุรอุทกสั่งเกณฑ์พวกพรานไปล้อมยิงฟานตายด้วยลูกศรอาบยาพิษ แล้วพากันแล่เนื้อเถือหนังกินกันจนทั่วถึง แต่กินเท่าไรก็ไม่หมด เนื่องจากพญานาคแสดงฤทธิ์ให้ฟานเผือกนั้นโตเท่าช้างสาร พระเจ้าสุรอุทกก็ทรงเสวยเนื้อฟานนั้นด้วยความอิ่มหนำสำราญ
พอตกกลางคืน เมื่อชาวเมืองเข้านอนกันหมดแล้ว พญานาคก็ดำลงไปใต้ดิน หนุนเมืองหนองหานหลวงให้ถล่มทลาย กลายเป็นอันเดียวกันกับหนองหาน ผู้คนพลเมืองล้มตายเป็นอันมาก ที่เหนือก็อพยพหลบลี้หนีอยู่ตามเกาะและตามฝั่ง
ส่วนพระเจ้าสุรอุทกนั้น ถูกพญานาคพันด้วยนาคบาศก์ ดึงลากไปสู่แม่น้ำโขงจนสิ้นพระชนม์ หนทางที่พญานาคาถึงลาดพระเจ้าสุรนอุทกไปนั้นเรียกว่าลำน้ำกรรมหรือลำน้ำก่ำในปัจจุบันนี้
พระเจ้าสุรอุทกมีโอรส 2 องค์ คือ เจ้าภิงคารและเจ้าคำแดง กุมารทั้งสอง ได้พาพลเมืองที่เหลือจากจมน้ำตาย ไปอาศัยอยู่ที่ดอนโพนเมือง ริมหนองหาน ทางทิศใต้ แล้วหาชัยภูมิที่จะสร้างเมืองใหม่ พอถึงภูน้ำลอดริมฝั่งหนองหาน เห็นว่าเป็นที่อุดมสมบูรณ์มีชัยภูมิที่ควรตั้งบ้านเมืองได้ จึงตั้งที่สักการะบูชาพระภูมิเจ้าที่ ตั้งสัตยาธิษฐานว่าจะสร้างบ้านเมือง ณ ที่นี้ ขอเทพยดาอารักษ์ผู้พิทักษ์ภูมิสถานที่นี้จงอภิบาลคุ้มครองไพร่ฟ้าประชาชนให้เป็นสุขสืบไปเทอญ
ขณะนั้นพญาสุวรรณนาคมีเกล็ดเป็นทองคำ ก็สำแดงตัวให้ปรากฏ ถือน้ำเต้าทองคำอันเป็นน้ำทิพย์ บอกว่าตนคือพญาสุวรรณนาค เฝ้าพิทักษ์รอยพระพุทธบาทอยู่ที่ภูน้ำลอดนี้ แล้วก็เอาน้ำหอมรดสรงอภิเษกเจ้าภิงคารให้เป็นพระยาเสวยเมืองมีชื่อว่า "พระยาสุวรรณภิงคาร" ปกครองไพร่ฟ้าประชาชนสืบมา
ส่วนเจ้าคำแดงผู้อนุชานั้น เสนาอำมาตย์ทางเมืองหนองหานน้อย ได้มาเชิญไปเสวยเมืองเป็นพญา แทนกษัตริย์ที่ว่างลง เรียกชื่อว่า "พญาคำแดงเมืองหนองหานน้อย" ตั้งแต่นั้นมา
พระยาสุวรรณภิงคาร จะครองเมืองหนองหานหลวงมากี่ปีไม่ปรากฏในอุรังคนิทานหรืออาจจะผลัดเปลี่ยนเจ้าผู้ครองเมืองมากี่องค์ก็ไม่มีหลักฐาน แม้แต่ในสมัยสมเด็จพระสัมมาสัมพุทธเจ้าโคดมก็ยังปรากฎว่าเจ้าพระยาสุวรรณภิงคาร ครองเมืองอยู่ ทั้งยังได้ราชาภิเษกกับพระนางเจ้านารายณ์เจงเวง ราชธิดาของพระเจ้ากรุงอินทปัทม์นคร เป็นเอกอัครมเหสีด้วย
ตอนที่ 2 แยกวงศ์ตระกูลมาจากเมืองกาฬสินธุ์
ตามถ้อยคำพระบรรเทา กรมการเมืองขุขันธ์เก่า กับถ้อยคำเพี้ยศรีครชุม ซึ่งเป็นหัวหน้าข้าปฏิบัติพระธาตุเชิงชุมเล่าว่า เมืองหนองหานหลวงเกิดฝนแล้งถึง 7 ปี เจ้าเมือง กรมการเมืองชาวชาติเขมร ซึ่งอยู่ในเมืองหนองหานหลวง ก็พากันอพยพกลับเมืองเขมรหมด เมืองหนองหานหลวงจึงเป็นเมืองร้าง
ต่อมาพระเจ้าแผ่นดินสยามได้ทรงพระกรุณาโปรดเกล้าฯ ให้อุปฮาดเมืองกาฬสินธุ์มารักษาพระธาตุเชิงชุม ซึ่งต่อมาได้เป็นพระธานี เจ้าเมืองสกลทวาปี
พ.ศ.2370 เจ้าอนุวงศ์ เจ้าเมืองเวียงจันทน์คิดกบฏต่อกรุงเทพมหานคร พระบาทสมเด็จพระนั่งเกล้าเจ้าอยู่หัว โปรดเกล้าฯ ให้กองทัพหลวงขึ้นไปปราบถึงเมืองเวียงจันทน์ แม่ทัพนายกองได้มาตรวจทัพถึงเมืองสกลทวาปี เจ้าเมือง กรมการเมืองไม่ได้เตรียมกำลังไพร่พลลูกกระสุนดินดำ เสบียงอาหารไว้ตามคำสั่งแม่ทัพ แม่ทัพจึงเอาตัวพระธานีไปประหารชีวิตเสีย แล้วกวาดต้อนครอบครัวไพร่พลเมือง เมืองสกลนครทวาปี ลงไปอยู่เมืองกบิลจันทคาม
ต่อมาแม่ทัพนายกองฝ่ายสยามได้ให้ราชวงศ์ลาวเมืองกาฬสินธุ์ มาเป็นผู้รักษาเมืองสกลทวาปี
ตอนที่ 3 แยกวงศ์ตระกูลมาจากเมืองนครพนม
ตามจดหมายเหตุพระปทุมฯ กรมการเมืองนครพนม กับจดหมายเหตุของพระยาประจันตประเทศธานี (โง่นคำ) เจ้าเมืองสกลนคร ได้กล่าวเมืองสกลนครดังต่อไปนี้ คือ
พ.ศ.2337 ตรงกับรัชกาลที่ 1 พระบรมราชา (พรหม) เจ้าเมืองนครพนม ถึงแก่กรรม นายสุตา ได้เป็นพระบรมราชา (สุตา) เจ้าเมืองนครพนม เจ้าจุลมี บุตรพระบรมราชา (พรหม) ได้เป็นพระพรหมอาษา เจ้าเมืองมหาขัยกองแก้ว
พ.ศ.2370 ตรงกับรัชกาลที่ 3 เจ้าอนุวงศ์ เจ้าเมืองเวียงจันทน์คิดกบฏ ทำศึกกับพระเจ้าแผ่นดินสยาม เมื่อพ่ายแพ้แก่กองทัพกรุงเทพฯ จึงหนีไปเมืองญวนและได้ไปพักกำลังอยู่ที่เมืองมหาชัย
พ.ศ.2375 กองทัพกรุงเทพฯ ยกขึ้นไปตีเมืองมหาชัย เมืองมหาชัยแตก กองทัพกรุงเทพฯ จับตัวภรรยาท้าวจุลนีอินกับพรรคพวก บ่าวไพร่ลงไปกรุงเทพฯ ต่อมาได้ไปอยู่เมืองพนัสนิคม
พ.ศ.2378 ท้าวจุลนีเมืองมหาชัย กับพรรคพวกซึ่งหลบหนีไปตอนเมืองมหาชัยแตก ได้เข้าหาแม่ทัพที่เมืองสกลทวาปี ขอสวามิภักดิ์ทำราชการจนชั่วลูกชั่วหลาน เมื่อลงไปเฝ้าพระเจ้าแผ่นดินสยามแล้วจึงได้รับภรรยามาตั้งบ้านเรือยอยู่ที่เมืองสกลทวาปี และต่อมาได้ไปเกลี้ยกล่อมกวาดต้อนชาวเมืองมหาชัยที่ตกค้างอยู่นั้นให้มาตั้งบ้านเรือนอยู่ในเมืองสกลทวาปีเป็นอันมาก
พ.ศ.2383 พระบาทสมเด็จพระนั่งเกล้าเจ้าอยู่หัว โปรดเกล้าฯ ให้ราชวงศ์คำ เป็นพระยาประเทศธานี เจ้าเมือง และเปลี่ยนนามเมืองใหม่เป็น "เมืองสกลนคร"
พ.ศ.2485 พระบาทสมเด็จพระนั่งเกล้าเจ้าอยู่หัว โปรดเหล้าให้ราชวงศ์อิน ขึ้นไปเกลี้ยกล่อมเจ้าเมืองวัง ได้ตัวท้าวโรงกลาง บุตรเจ้าเมืองวังกับพรรคพวกบ่าวไพร่ชาวผู้ไทยเป็นอันมาก พร้อมกับเพี้ยเมืองสูง เพี้ยขุดโคด หัวหน้าข่ากะโซ่ กับครอบครัวบ่าวไพร่ข่ากะโซ่ ข้ามแม่น้ำโขงมาตั้งบ้านเรือนอยู่ในเขตแขวงเมืองสกลนคร เป็นอันมาก
พ.ศ.2387 พระบาทสมเด็จพระนั่งเกล้าเจ้าอยู่หัว โปรดเกล้าฯ ตั้งเมืองพรรณานิคม เมืองกุสุมาลย์มณฑล ให้เป็นเมืองขึ้นเมืองสกลนคร ตั้งให้ท้าวโรงกลางเป็นพระเสนาณรงค์ เจ้าเมืองพรรณานิคม
พ.ศ.2418 พวกฮ่อได้เข้ามาทำการจราจลถึงเมืองเวียงจันทน์ ในเขตแขวงเมืองหนองคาย เมืองสกลนครถูกเกณฑ์กำลัง 1,000 คน ไปช่วยปราบฮ่อในครั้งนี้ด้วย
พ.ศ.2421 ราชวงศ์ปิด ได้เป็นพระยากระจันตประเทศธานี เจ้าเมืองสกลนคร
พ.ศ.2427 พวกฮ่อที่หนีกองทัพกรุงเทพฯ ที่เมืองเวียงจันทน์ ไปตั้งค่ายมั่นอยู่ที่ทุ่งเชียงคำ เมืองสกลนครถูกเกณฑ์พล กำลัง 1,000 คน ช้าง 25 เชือก โคต่าง 100 ตัว ข้าวสาร 3,000 ถัง ไปปราบฮ่อครั้งนี้
พ.ศ.2430 อุปฮาดโง่นคำเมืองสกลนคร ได้เป็นพระยาประจันตประเทศธานี เจ้าเมืองสกลนคร เป็นต้นสกุล "พรหมสาขา ณ สกลนคร"
พ.ศ.2439 โปรดเกล้าฯ ให้เมืองกุสุมาลย์ เมืองโพธิไพศาล เมืองขึ้นสกลนคร ไปขึ้นเมืองนครพนม และโปรดเกล้าฯ ให้เมืองวาริชภูมิ เมืองขึ้นเมืองหนองหานหลวง มาขึ้นเมืองสกลนคร
พ.ศ.2456 มหาอำมาตย์โท พระยามหาอำมาตยาธิบดี รองเสนาบดีกระทรวงมหาดไทย มาตรวจราชการเมืองสกลนคร ให้ยุบอำเภอวาริชภูมิ แล้วแบ่งท้องที่อำเภอวาริชภูมิไปขึ้นอยู่ในความปกครองของอำเภอพรณรานิคม 3 ตำบล และยุบอำเภอกุสุมาลย์ แล้วโอนท้องที่อำเภอกุสุมาลย์มาขึ้นกับอำเภอเมืองสกลนคร และขึ้นกับอำเภอเมืองนครพนมด้วย
นอกจากนี้ยังยุบอำเภออากาศอำนวยแล้วโอนท้องที่ไปขึ้นกับอำเภอวานรนิวาส แขวงเมืองสกลนคร และขึ้นกับอำเภอท่าอุเทน แขวงเมืองนครพนมด้วย
พ.ศ.2459 ทางราชการให้เปลี่ยนคำนำหน้าเมืองว่า จังหวัด เมืองสกลนครให้เรียกว่า จังหวัดสกลนคร เปลี่ยนนามอำเภอเมืองเป็นอำเภอธาตุเชิงชุม เปลี่ยนนามตำบลตะวันตำในเมืองเป็นตำบลสะพานหิน เปลี่ยนนามตำบลตะวันออกในเมืองเป็นตำบลธาตุเชิงชุม
พ.ศ.2494 จังหวัดที่เคยเป็นมณฑลอุดร และมณฑลร้อยเอ็ดเดิม ได้มีพระราชกฤษฎีกา ตั้งขึ้นเป็นภาค 4 มีผู้ว่าราชการภาคเป็นผู้รับผิดชอบ
พ.ศ.2499 ได้มีพระราชบัญญัติเลิกภาค และให้แต่ละจังหวัดปกครองตนเองโดยมีผู้ว่าราชการจังหวัดเป็นผู้รับผิดชอบ ขึ้นตรงต่อกระทรวงมหาดไทย และให้แบ่งเขตการปกครองภายในจังหวัดออกเป็นอำเภอ และเปลี่ยนอำเภอธาตุเชิงชุมเป็นอำเภอเมืองสกลนครมาจนถึงปัจจุบัน