โรงเรียนบ้านโนนสูง เดิมชื่อว่า โรงเรียนประชาบาลตำบลแขม 4 (วัดบ้านโนนสูง) ตั้งขึ้น  เมื่อวันที่ 13 มิถุนายน พ.ศ. 2482  ซึ่งมีขุนวัติกรรมรักเป็นนายอำเภอ  ได้อาศัยวัดบ้านโนนสูงเป็นที่เรียน  พ.ศ. 2493  กรมสามัญศึกษา  กระทรวงศึกษาธิการ ได้ตั้งเป็นโรงเรียนเอกเทศถาวร  มีชื่อใหม่ว่า “โรงเรียนบ้านโนนสูง” จนถึงทุกวันนี้  และแต่งตั้งให้ นายนิรัติ หลาวทอง   เป็นครูใหญ่คนแรก ของโรงเรียนบ้านโนนสูง                

                โรงเรียนบ้านโนนสูง  มีหมู่บ้านในเขตบริการทั้งหมด  4  หมู่บ้าน คือ บ้านโนนเค็ง หมู่ที่ 6   บ้านโนนสูง  หมู่ที่  7  บ้านโนนแตน หมู่ที่  8  และบ้านเหงี่ยงอีทวด หมู่ที่  10 

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

                พ.ศ. 2527  เปิดสอนชั้นเด็กเล็ก ถึงชั้นประถมศึกษาปีที่ 6  พ.ศ. 2537  เปิดสอนชั้นอนุบาล 1  ถึง ชั้น ประถมศึกษาปีที่ 6   พ.ศ.2539  เปิดสอนชั้นมัธยมศึกษาปีที่ 1  ตามโครงการขยายโอกาสทางการศึกษา 

                พ.ศ. 2543  ได้รับบริจาคจาก พ.ต.ท.สันติ   ศศิภูริ  นายวิวัฒน์  วิวัฒรางกูล  และนายสมพงษ์ นรินทร์สุขสันติ โดยการประสานงานของพ.ต.อ.ประเสริฐ สุทธิสนธิ์ สร้างห้องสมุดเอกเทศ  ขนาด 8 X 20  เมตร  พร้อมอุปกรณ์ รวมมูลค่าทั้งสิ้น  822,000  บาท

                พ.ศ. 2552  โรงเรียนบ้านโนนสูง ได้เข้าร่วมโครงการโรงเรียนในฝัน รุ่นที่ 3 (โรงเรียนดีประจำอำเภอ)  และได้รับการตรวจเยี่ยมเพื่อรับรองเป็นโรงเรียนต้นแบบโรงเรียนในฝัน เมื่อวันที่ 10  มีนาคม พ.ศ.2554 โดยคณะกรรมการจากสำนักงานคณะกรรมการการศึกษาขั้นพื้นฐาน ผลการตรวจเยี่ยม  โรงเรียนบ้านโนนสูง ได้รับการประเมินคะแนนอยู่ในระดับดีมาก  เป็นโรงเรียนลำดับที่ 39  ของประเทศ จากจำนวน  841  โรงเรียน และเป็นโรงเรียนประถมศึกษาโรงเรียนแรกของประเทศที่ได้รับการตรวจเยี่ยมและรับรองให้เป็นโรงเรียนต้นแบบโรงเรียนในฝัน รุ่นที่ 3 (โรงเรียนดีประจำอำเภอ)

                 ปัจจุบันโรงเรียนบ้านโนนสูง มีอาคารเรียน 3  หลัง  บ้านพักครู  1  หลัง โรงฝึกงาน 1 หลัง  ห้องประชุม  1  หลัง  ส้วม  13  ที่  ห้องสมุด  1  หลัง  หอศิลปะ  1  หลัง  มีครูประจำการ 11  คน  พนักงานราชการ  1  คน  มีนักเรียนทั้งหมด  149  คน เปิดสอนตั้งแต่ชั้นอนุบาล 1  ถึงชั้นมัธยมศึกษาปีที่ 3  ผู้บริหารโรงเรียนคนปัจจุบัน  คือ  นางนันทิยา   พรหมทา