โรงเรียนมุกดาลัย เดิมชื่อว่า โรงเรียนประจำอำเภอมุกดาหาร “ทรงวิทยา”
ตั้งขึ้นเมื่อ พ.ศ. 2453 สมัยพระยาสมุทรศักดารักษ์ ดำรงตำแหน่งเป็นนายอำเภอมุกดาหาร โดยมี นายหนู ศรีสุริยจันทร์ ดำรงตำแหน่งเป็นครูใหญ่คนแรก ต่อมา พ.ศ. 2461 เมื่อสมัย รองอำมาตย์โทขุนผดุงนิคมเขต(พระปทุมเทวาภิบาล)เป็นนายอำเภอ นายคี รัตนกาล ครูใหญ่ ได้ขอบริจาคเงินจากประชาชน และข้าราชการ ก่อสร้างอาคารเรียนถาวร ก่ออิฐถือปูนทรงมะลิลาขึ้นตามแบบแปลนของอำมาตย์เอกพระยาพนมคธานุรักษ์ ผู้ว่าราชการจังหวัดนครพนม โดยมีนายอำเภอเมืองมุกดาหารเป็นผู้ควบคุมการก่อสร้างและก่อสร้างในที่นาของราษฎร ซึ่งมีขนาดกว้าง 93 เมตร ยาว 280 เมตรโดยมีอาณาเขตดังนี้
ทิศเหนือ จด ถนนพิทักษ์พนมเขต
ทิศใต้ จด ที่ราษฎร
ทิศตะวันออก จด ถนนพิทักษ์สันติราษฎร์
ทิศตะวันตก จด ถนนแก้วกินรี
การก่อสร้างอาคารเรียนได้เสร็จเรียบร้อยใน พ.ศ. 2464 รวมค่าก่อสร้างทั้งสิ้น 8,826 บาท 29 สตางค์ และทำพิธีเปิดเมื่อวันที่ 20 พฤษภาคม 2464 ได้จัดงานฉลองอาคารเรียนหลังใหม่ พร้อมกับเปลี่ยนชื่อโรงเรียน “ทรงวิทยา” เป็นโรงเรียนประจำอำเภอมุกดาหาร “มุกดาลัย” โดยได้รับพระราชทานนามจากพระบาทสมเด็จพระมงกุฎเกล้าเจ้าอยู่หัว รัชกาลที่ 6
พ.ศ. 2495 นายสง่า ไทยยานนท์ นายอำเภอเมืองมุกดาหาร นายสมชาย จันทรผล ศึกษาธิการอำเภอ นายเบ็ง จันทรโคตร ครูใหญ่ ได้ขอเปลี่ยนชื่อจาก “มุกดาลัย” เป็น
“มุกดาวิทยาลัย” แต่ไม่ได้รับอนุญาตจึงยังคงเป็นโรงเรียนมุกดาลัยอยู่เช่นเดิม
โรงเรียนมุกดาลัยได้ดำเนินการปรับปรุงซ่อมแซมอาคารเรียนอยู่ตลอดเวลา เพื่อให้เหมาะสม
กับจำนวนนักเรียนที่เพิ่มขึ้นอยู่ตลอดเวลา
ในปี พ.ศ. 2497 นายชูสง่า ไชยพันธ์ นายนินทร์ ศิริมาตย์ ศึกษาธิการ นายเบ็ง
จันทรโคตร ครูใหญ่ได้จัดสร้างโรงอาหาร ห้องน้ำ ห้องส้วม ขึ้นในปี พ.ศ. 2501 เกิดวาตภัยร้ายแรง อาคารได้รับความเสียหาย จึงของบประมาณซ่อมแซมใน พ.ศ. 2502 โดยได้รับงบประมาณ 22,000 บาท ในสมัยนายสิทธิ์ ณ นครพนม เป็นนายอำเภอนายมานะ อินทรเจริญศักดิ์ เป็นศึกษาธิการอำเภอ
พ.ศ. 2509 โรงเรียนมุกดาลัยได้โอนไปสังกัดองค์การบริหารส่วนจังหวัดกระทรวงมหาดไทย และได้สร้างอาคารเรียนครึ่งตึกครึ่งไม้โดยใช้งบประมาณ 100,000 บาท พ.ศ. 2513 นายเฉิดศักดิ์ แสนวิเศษ ได้มาดำรงตำแหน่งครูใหญ่ และอาจารย์ใหญ่ในเวลาต่อมาและในปีนี้ได้รับงบประมาณก่อสร้างอาคารไม้ชั้นเดียว จำนวน 103,000 บาท
พ.ศ. 2520 ได้รับงบประมาณสร้างอาคารเรียนครึ่งตึกครึ่งไม้สองชั้น จำนวน 1 หลัง
และยุวสมาคมแห่งประเทศไทยมุกดาหาร ได้สร้างสนามบาสเกตบอลพื้นคอนกรีต ขนาดกว้าง 10 เมตร ยาว 15 เมตร และผู้ปกครองนักเรียนได้สร้างเวทีกลางแจ้งให้ ขนาดกว้าง 6 เมตร
ยาว 12 เมตร สูง 1 เมตร
พ.ศ. 2523 สมาคมครู ผู้ปกครองนักเรียนได้ก่อสร้างถนนคอนกรีต ขนาด กว้าง 4 เมตร ยาว 61 เมตร หนา 15 เซนติเมตร ให้โรงเรียน และเมื่อวันที่ 1 ตุลาคม พ.ศ. 2523 ทางราชการได้โอนโรงเรียนไปสังกัดสำนักงานคณะกรรมการการประถมศึกษาแห่งชาติกระทรวงศึกษาธิการ
พ.ศ. 2527 ยุวสมาคมแห่งประเทศไทยจังหวัดมุกดาหาร ได้สร้างลานคอนกรีตอเนกประสงค์ ขนาดกว้าง 21 เมตร ยาว 36 เมตร ให้โรงเรียนและได้รับงบประมาณก่อสร้างอาคารเรียน 3 ชั้น และ สปช. 406/2526 โดยมีสำนักงานการประถมศึกษาจังหวัดมุกดาหารยืมใช้เป็นอาคารสำนักงาน
พ.ศ. 2532 - 2536 ได้รับงบประมาณจากทางราชการ จำนวน 4 รายการ คือ ปรับปรุงสนามฟุตบอล สร้างสนามวอลเลย์บอล ถนนคอนกรีต ปรับปรุงระบบประปา ซ่อมแซมไฟฟ้าในโรงเรียนและนอกจากนั้นชุมชนยังได้บริจาคเงินเพื่อสร้างและปรับปรุงด้านอาคารสถานที่ให้แก่โรงเรียน ดังนี้
ปรับปรุงซุ้มประตูพิทักษ์สันติราษฏร์ ซุ้มประตูแก้วกินรี ถนนคอนกรีต สร้างซุ้มประตู
เทวาภิบาล ซุ้มประตูคุ้มเจ้าเมือง สร้างสวนสุขภาพราวิน ธนบัตร สนามเด็กเล่น ลานคอนกรีต ทางเท้าร่องระบายน้ำรอบอาคารเรียน
ในเดือนมีนาคม พ.ศ. 2537 นายปรีชา ทองบพิตร ได้รับการแต่งตั้งเป็น ผู้อำนวยการโรงเรียนระดับ 9 จนถึงเดือน กันยายน พ.ศ. 2537 ได้เกษียณอายุราชการ โดยมีนายอมร ศรีสุริยจันทร์ เป็นผู้รักษาการในตำแหน่ง
วันที่ 27 มิถุนายน 2550 โรงเรียนมุกดาลัยได้รับเงินบริจาค จากพ่อค้า ประชาชน ครูและผู้ปกครองนักเรียน จำนวน 164,487 บาทในการปรับปรุง ก่อสร้างป้ายโรงเรียนแบบถาวร
วันที่ 27 เดือน ตุลาคม 2551 นายประทีป โรจนาพงษ์ ได้รับการแต่งตั้งให้ดำรงตำแหน่งผู้อำนวยการโรงเรียนมุกดาลัย จนถึงปี พ.ศ. 2557
วันที่ 2 ธันวาคม 2551 มหาวิทยาลัยอุบลราชธานี ได้ใช้พื้นที่โรงเรียนมุกดาลัย ก่อสร้าง ศูนย์การเรียนรู้เทคโนโลยี งบประมาณ 19,200,000 บาท
วันที่ 17 ธันวาคม 2551 บริษัทมณีรัตน์พืชผล จำกัดโดยคุณมณีรัตน์ นวกุลกาญจนภาส ศิษย์เก่าโรงเรียนมุกดาลัย บริจาคโต๊ะเก้าอี้นักเรียนจำนวน 100 ชุด คิดเป็นมูลค่า 170,000 บาท
วันที่ 17 มกราคม 2552 บริษัทมณีรัตน์พืชผล จำกัด โดยคุณมณีรัตน์ นวกุลกาญจนภาส ศิษย์เก่าโรงเรียนมุกดาลัยบริจาคโต๊ะเก้าอี้นักเรียนจำนวน 100 ชุด คิดเป็นมูลค่า 170,000 บาท และบริษัทไร่ธัญญะ จำกัด โดยนางอัจฉรา เลิศสกุลเจริญและนางกาญจนา เลิศสกุลเจริญ บริจาคโต๊ะเก้าอี้นักเรียนจำนวน 100 ชุด คิดเป็นมูลค่า 170,000 บาท
วันที่ 30 มีนาคม 2552 ได้รับงบประมาณจากจังหวัดมุกดาหาร โดยนายประณีต บุญมี ผู้ว่าราชการจังหวัดมุกดาหาร จำนวน 200,000 บาท ในการจัดซื้อวัสดุ ครุภัณฑ์เครื่องดนตรีสากล เครื่องดุริยางค์
วันที่ 21 ธันวาคม 2552 สมเด็จพระเทพรัตนราชสุดาสยามบรมราชกุมารี เสด็จพระราชดำเนินโรงเรียนมุกดาลัย ทรงเปิดอาคาร “เทพรัตนคุณูปการ” ของมหาวิทยาลัยอุบลราชธานี วิทยาเขตมุกดาหาร
วันที่ 1 ธันวาคม 2553 บริษัทมณีรัตน์พืชผล จำกัด โดยคุณมณีรัตน์ นวกุลกาญจนภาส ศิษย์เก่าโรงเรียนมุกดาลัย บริจาคคอมพิวเตอร์พร้อมโต๊ะ จำนวน 30 ชุด คิดเป็นมูลค่า 450,000 บาท เนื่องในโอกาสโรงเรียนมุกดาลัย ครบรอบ 100 ปี
วันที่ 2 สิงหาคม 2554 บริษัท เด็ดดอกรักทรานสปอร์ต บริจาคทรัพย์เพื่อก่อสร้างส้วม จำนวน 3 ที่ คิดเป็นมูลค่า 150,000 บาท
วันที่ 15 เมษายน 2555 กองสลากกินแบ่งรัฐบาล บริจาคทรัพย์ จำนวน 300,000 บาท ในการจัดซื้อสื่อการเรียนการสอนห้องภาษาต่างประเทศ (ภาษาเวียดนาม) เนื่องในโอกาสโรงเรียนมุกดาลัยครบรอบ 101 ปี
วันที่ 15 เมษายน 2555 บริษัทมณีรัตน์พืชผล จำกัด โดยคุณมณีรัตน์ นวกุลกาญจนภาส ศิษย์เก่าโรงเรียนมุกดาลัย บริจาคทรัพย์เป็นเงิน 170,000 บาท เพื่อก่อสร้างซุ้มประตูทางเข้าด้านหน้าโรงเรียน ฝั่งตรงข้ามโรงพยาบาลมุกดาหาร เนื่องในโอกาสโรงเรียนมุกดาลัยครบรอบ 101 ปี
วันที่ 15 เมษายน 2555 ดร.อีดิธ นามประกาย ประธานกรรมการ บริษัทโตโยต้ามุกดาหาร (1993) จำกัด บริจาคทรัพย์เป็นเงิน 170,000 บาท เพื่อก่อสร้างซุ้มประตูทางเข้าด้านหน้าโรงเรียน
ฝั่งตรงข้ามไปรษณีย์มุกดาหาร เนื่องในโอกาสโรงเรียนมุกดาลัยครบรอบ 101 ปี
วันที่ 15 เมษายน 2555 สมาคมศิษย์เก่าผู้ปกครองและครูโรงเรียนมุกดาลัย ระดมทุนและ ทรัพยากรในการก่อสร้างรั้วโรงเรียน จำนวน 64 ช่อง ๆ ละ 20,000 บาท เนื่องในโอกาสโรงเรียนมุกดาลัยครบรอบ 101 ปี รวมเป็นเงิน 1,280,000.- บาท
วันที่ 7 เดือนเมษายน พ.ศ. 2559 นายศุภศิษฐ อินทรวิเศษ ย้ายมาดำรงตำแหน่งผู้อำนวยการโรงเรียนมุกดาลัย จนถึง พ.ศ.2561
วันที่ 8 เดือนพฤศจิกายน พ.ศ. 2561 ดร.ชาติชาย ก่อคุณ ย้ายมาดำรงตำแหน่งผู้อำนวยการโรงเรียนมุกดาลัย จนถึงปัจจุบัน