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

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

กองอุทยานแห่งชาติ จึงทำการสำรวจอย่างจริงจัง ในปี พ.ศ. 2531 และเริ่มดำเนินการจัดตั้ง ตั้งแต่ปี พ.ศ. 2532 เป็นต้นมา ซึ่งได้ประกาศให้เป็นอุทยานแห่งชาติโดยได้มีพระราชกฤษฏีกากำหนดที่ดินป่าดงบังอี่ แปลงที่สาม และป่าดงบังอี่ แปลงที่สี่ ในท้องที่ตำบลดงเย็น อำเภอเมืองมุกดาหาร ตำบลนาอุดม ตำบลนิคมคำสร้อย ตำบลโชคชัย อำเภอนิคมคำสร้อย และตำบลเหล่าหมี ตำบลป่าไร่ ตำบลบ้านบาก อำเภอดอนตาล จังหวัดมุกดาหาร ป่าดงบังอี่ในท้องที่ตำบลกุดแห่ ตำบลบุ่งค้า อำเภอเลิงนกทา จังหวัดยโสธร ป่าดงบังอี่ฝั่งซ้ายห้วยทมในท้องที่ตำบลคำเขื่อนแก้ว อำเภอชานุมาน จังหวัดอุบลราชธานี และป่าดงหัวกอง และป่าดงบังอี่ ในท้องที่ตำบลเสนางคนิคม ตำบลโพนทอง ตำบลหนองไฮ อำเภอเสนางคนิคม จังหวัดอุบลราชธานี ประกาศในราชกิจจานุเบกษา เล่ม 109 ตอนที่ 126 ลงวันที่ 30 ธันวาคม 2535 นับเป็นอุทยานแห่งชาติลำดับที่ 75 ของประเทศไทย