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

ประวัติความเป็นมา

          ด้วยกองอุทยานแห่งชาติ ได้รับรายงานจากป่าไม้จังหวัดมุกดาหาร ตามหนังสือที่ มห.0009/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 เห็นชอบให้กำหนดพื้นที่ดังกล่าวเป็นอุทยานแห่งชาติได้  โดยได้มีพระราชกฤษฎีกากำหนดบริเวณที่ดินป่าดงบังอี้ ในท้องที่ตำบลศรีบุญเมือง ตำบลคำอาฮวน ตำบลดงเย็น ตำบลนาสีนวน อำเภอเมือง และตำบลบ้านแก้ง อำเภอดอนตาล จังหวัดมุกดาหาร ให้เป็นอุทยานแห่งชาติในปี พ.ศ. 2531 ประกาศไว้ในราชกิจจานุเบกษาเล่ม 105 ตอนที่ 235 ลงวันที่ 28 ธันวาคม พ.ศ.2531 นับเป็นอุทยานแห่งชาติแห่งที่ 59 ของประเทศ