ในปี 2527 กองอุทยานแห่งชาติ ได้รับรายงานจากป่าไม้จังหวัดมุกดาหารตามหนังสือ ที่ มห 009/6913 ลงวันที่ 24 เมษายน 2527 ว่า จังหวัดได้รับนโยบายจาก ฯพณฯ รัฐมนตรีว่าการกระทรวงเกษตรและสหกรณ์ ให้ดำเนินการอนุรักษ์ป่าใกล้จังหวัดและอำเภอต่างๆ ในรูปอุทยานแห่งชาติ วนอุทยาน หรือสวนรุกขชาติ เป็นการอนุรักษ์ทรัพยากรธรรมชาติ ซึ่งจังหวัดได้สำรวจสภาพพื้นที่ที่เหมาะสมควรจัดตั้งเป็นอุทยานแห่งชาติหรือวนอุทยานแล้ว

กองอุทยานแห่งชาติ กรมป่าไม้ ได้มีคำสั่งที่ 1260/2527 ลงวันที่ 16 สิงหาคม 2527 ให้นายเชิดชัย นิลัมภาชาต เจ้าพนักงานธุรการ 4 และนายพงษ์ศักดิ์ จักรกุล พนักงานพิทักษ์ป่า ไปดำเนินการสำรวจหาข้อมูลเบื้องต้นในท้องที่ตำบลบ้านแก้ง อำเภอดอนตาล ตำบลนาสีนวล อำเภอเมือง จังหวัดมุกดาหาร จากรายงานการสำรวจตามหนังสือลงวันที่ 22 ตุลาคม 2527 ปรากฏว่า บริเวณภูนางหงษ์ ภูถ้ำพระ ภูหลังเส ภูหินเทิบ และภูมโน อยู่ในเขตป่าสงวนแห่งชาติดงบังอี้ เนื้อที่ประมาณ 49.26 ตารางกิโลเมตร มีสภาพเป็นภูเขาสูงชันเป็นเทือกเขาติดต่อกัน มีป่าเบญจพรรณ ป่าเต็งรัง มีหน้าผาสูง และลานหินกว้างและยาว ประกอบด้วยหินรูปร่างต่างๆ วางซ้อนทับกันอยู่ มีถ้ำที่สวยงาม

กองอุทยานแห่งชาติได้มีหนังสือ ที่ กษ 0713/4655 ลงวันที่ 11 ธันวาคม 2527 เสนอกรมป่าไม้เห็นควรจัดตั้งเป็นอุทยานแห่งชาติ และมีคำสั่งกรมป่าไม้ที่ 1951/2527 ลงวันที่ 13 ธันวาคม 2527 ให้นายศักดิ์สิทธิ์ พลทรัพย์ศิริ เจ้าพนักงานป่าไม้ 3 ไปดำเนินการจัดตั้งบริเวณดังกล่าวเป็นอุทยานแห่งชาติ ซึ่งได้มีหนังสือ ที่ กษ 0713(มห)/1 ลงวันที่ 30 มกราคม 2528 รายงานการสำรวจพื้นที่ดังกล่าวว่ามีความเหมาะสมที่จะจัดตั้งเป็นอุทยานแห่งชาติ ให้กองอุทยานแห่งชาติดำเนินการต่อไป

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

จังหวัดมุกดาหารได้นำเสนอเข้าที่ประชุมคณะอนุกรรมการป้องกันอนุรักษ์ทรัพยากรป่าไม้จังหวัด ครั้งที่ 2/2530 เมื่อวันที่ 22 กรกฎาคม 2530 ได้มีมติสนับสนุนให้ประกาศเป็นอุทยานแห่งชาติ ซึ่งคณะกรรมการอุทยานแห่งชาติได้มีมติคราวประชุมครั้งที่ 1/2530 เมื่อวันที่ 18 มิถุนายน 2530 เห็นชอบให้กำหนดพื้นที่ดังกล่าวเป็นอุทยานแห่งชาติได้ โดยได้มีพระราชกฤษฎีกากำหนดบริเวณที่ดินป่าดงบังอี้ ในท้องที่ตำบลศรีบุญเมือง ตำบลคำอาฮวน ตำบลดงเย็น ตำบลนาสีนวน อำเภอเมือง และตำบลบ้านแก้ง อำเภอดอนตาล จังหวัดมุกดาหาร

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

ลักษณะภูมิอากาศ
อุทยานแห่งชาติมุกดาหาร มีสภาพภูมิอากาศแบ่งออกเป็น 3 ฤดู คือ ฤดูฝน ระหว่างเดือนมิถุนายน - เดือนพฤศจิกายน ฤดูหนาว ระหว่างเดือนธันวาคม - เดือนมกราคม ฤดูร้อน ระหว่างเดือนกุมภาพันธ์ - เดือนพฤษภาคม

พืชพรรณและสัตว์ป่า
สภาพป่าประกอบด้วย ป่าเบญจพรรณ และป่าเต็งรังตามธรรมชาติ มีพันธุ์ไม้นานาชนิด ได้แก่ ตะแบก พยอม พะยูง ตะเคียน ประดู่ แดง มะไฟ มะค่า ชิงชัน กระบก กระบาก ส้าน จิก ติ้ว จำปีป่า ยมหอม เหียง เต็ง รัง เป็นต้น

สัตว์ป่าที่พบเห็นโดยส่วนใหญ่เป็นสัตว์ขนาดเล็ก ได้แก่ หมูป่า กวางป่า เก้ง หมาจิ้งจอก ลิง กระต่าย นกยูง ไก่ป่า ไก่ฟ้า และนกนานาชนิด

ถ้ำฝ่ามือแดง
เป็นเพิงหินกว้าง 3 เมตร ยาว 60 เมตร มีรูปรอยฝ่ามือสีแดงติดผนังถ้ำ ซึ่งมีลักษณะเป็นการจุ่มสีแล้วทาลงไปบนผนังหิน 2 มือ และอีก 4 มือ เป็นร่องรอยการวางมือทาบบนผนังหินแล้วใช้สีทับ เป็นร่องรอยการสื่อความหมายของมนุษย์ยุคก่อนประวัติศาสตร์อายุประมาณ 3,000 ปี ถ้ำฝ่ามือแดงอยู่บริเวณหน่วยพิทักษ์อุทยานแห่งชาติที่ มห.1 (ห้วยสิงห์) ทางเข้าอยู่ริมทางหลวงจังหวัดหมายเลข 2034 ประมาณกิโลเมตรที่ 8-9 การไปชมถ้ำควรมีเจ้าหน้าที่นำทาง เพราะเป็นเส้นทางเดินป่าใช้เวลาประมาณชั่วโมงครึ่ง
กิจกรรม -เที่ยวถ้ำ/ธรณีวิทยา - ชมประวัติศาสตร์

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

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

ภูผาเทิบ
เป็นภูผาที่มีหินมาเทิบทับกันไว้ มีกลุ่มหินประกอบด้วยหินรูปร่างลักษณะต่างๆ วางซ้อนกันอยู่อย่างวิจิตรพิสดาร บนลานหินกว้างและยาวเป็นสวนหินเปรียบเสมือนประติมากรรมธรรมชาติ หินบางก้อนมีรูปร่างคล้ายเครื่องบินไอพ่น รอบเท้าบู้ท เก๋งจีน มงกุฎ และคล้ายสถูป เป็นต้น บริเวณลานหินมีป่าเต็งรังที่มีลักษณะแคระแกร็นสวยงาม และในฤดูฝนต่อฤดูหนาวจะเต็มไปด้วยไม้ดอกงดงามนานาชนิด อยู่ห่างจากที่ทำการอุทยานแห่งชาติประมาณ 100 เมตร
กิจกรรม -ชมพรรณไม้ - เที่ยวถ้ำ/ธรณีวิทยา

ภูนางหงษ์
มีหินธรรมชาติเป็นรูปคล้ายหงษ์ขนาดใหญ่อยู่กลางลานหินกว้าง และมีก้อนหินขนาดใหญ่วางทับกันเป็นรูปร่างและสีต่าง ๆ กัน
กิจกรรม -ชมทิวทัศน์

วังเดือนห้า
เป็นแอ่งน้ำซึ่งจุน้ำฝนที่ไหลเป็นธารมาจากลานหินสามารถที่จะลงไปแช่และอาบน้ำเล่นได้อย่างสบาย อยู่ไม่ไกลจากที่ทำการอุทยานแห่งชาติ
กิจกรรม -ชมพรรณไม้ - ชมทิวทัศน์

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

ภูมโน

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

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

ลานมุจลินท์
จากกลุ่มหินเทิบเดินไปอีก 300 เมตร จะพบกับลานหินเรียบที่ทอดตัวยาวล้อมรอบด้วยป่าเต็งรัง
กิจกรรม -เที่ยวถ้ำ/ธรณีวิทยา

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

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

สถานที่ติดต่อ
อุทยานแห่งชาติมุกดาหาร
อ. เมืองมุกดาหาร จ. มุกดาหาร 49000
โทรศัพท์ 0 4260 1753

การเดินทาง
รถยนต์
ที่ทำการอุทยานแห่งชาติ ตั้งอยู่บริเวณภูผาเทิบ อยู่ห่างจากอำเภอเมือง จังหวัดมุกดาหาร ประมาณ 17 กิโลเมตร โดยเดินทางไปตามเส้นทางสายมุกดาหาร-อำเภอดอนตาล ประมาณ 14 กิโลเมตร เป็นถนนลาดยาง แล้วเลี้ยวซ้ายไปตามถนนลูกรังอีก 2 กิโลเมตร จะถึงอุทยานแห่งชาติมุกดาหาร

ที่พักแรม/บ้านพัก
มีบ้านพักให้บริการแก่นักท่องเที่ยว

ที่จอดรถ
มีที่จอดรถให้บริการแก่นักท่องเที่ยว

ศูนย์บริการนักท่องเที่ยว
มีศูนย์บริการนักท่องเที่ยว ให้บริการข้อมูลเกี่ยวกับอุทยานแห่งชาติ นักท่องเที่ยวสามารถเข้ามาขอรับบริการข้อมูลได้ทุกวัน ไม่เว้นวันหยุดราชการ ระหว่างเวลา 8.00 - 16.30 น.