โรงเรียนบ้านผือฮีนาลานจาน จัดตั้งขึ้นเมื่อวันที่ 6 กรกฎาคม พ.ศ. 2466  โดยอาศัยศาลาการเปรียญวัดบ้านผือฮี เป็นสถานที่เล่าเรียน มีชื่อว่าโรงเรียนสาขาประชาบาล ตำบลไผ่ 1 (วัดบ้านผือฮี) เป็นสาขาของโรงเรียนสาขาประชาบาลตำบลไผ่ (วัดบ้านสร้างช้าง) มีหมู่บ้านในเขตพื้นที่บริหาร 4 หมู่บ้านคือ บ้านผือฮี บ้านนาลา

บ้านนาจาน และบ้านชาด

                   วันที่ 6 พฤษภาคม 2477 ได้จัดตั้งโรงเรียนอิสระขึ้น มีชื่อว่าโรงเรียนประชาบาลตำบลไผ่

(วัดบ้านผือฮี) 

                   วันที่ 28 มิถุนายน 2486 ได้แยกไปตั้งสาขาโรงเรียนบ้านชาด

                   วันที่ 18 พฤษภาคม 2492 นายสา พรหมสาน ครูใหญ่ พร้อมด้วยราษฎรได้ย้ายสถานที่เรียนจากวัดบ้านผือฮีมาตั้งที่ที่ดินแห่งใหม่ ซึ่งมีผู้บริจาคให้

                   พ.ศ. 2523 – 2526 ได้งบพัฒนาจังหวัดสร้างซุ้มประตูทางด้านทิศใต้และรั้วลวดหนาม และอาคารเอนกประสงค์ แบบ ยส. 201 ราคา 160,000 บาท

                   พ.ศ. 2527 ได้งบต่อเติมอาคารเรียนหลังเดิม (ปัจจุบันรื้อถอนแล้ว)

                   พ.ศ. 2530 ได้งบก่อสร้างอาคารเรียน แบบ สปช. 102/24 ขนาด 4 ห้องเรียน ราคา 700,000 บาท พร้อมถังเก็บน้ำฝนแบบ ฝ.33 ราคา 44,000 บาท

                   ต่อมาได้เปลี่ยนชื่อโรงเรียนใหม่ว่า โรงเรียนบ้านผือฮีนาลานาจาน มีหมู่บ้านในเขตพื้นที่บริการ 3 หมู่บ้าน คือ บ้านผือฮี หมู่ 6 บ้านนาลา หมู่ 5 และบ้านนาจาน หมู่ 4 ตำบลนาสะไมย์ อำเภอเมือง จังหวัดยโสธร

                   พ.ศ. 2548 ได้รับงบประมาณก่อสร้างอาคารเรียนแบบ สปช. 103/26 ขนาด 3 ห้องเรียน จำนวน 1 หลัง ราคา 970,000 บาท จากทางราชการ

                   พ.ศ. 2549 ได้รับงบประมาณปรับปรุงโรงอาหาร ห้องพยาบาล โดยใช้เงินอุดหนุนรายหัว และขอบริจาคจากผู้ปกครองนักเรียน เป็นเงิน 49,275 บาท และจัดทำผ้าป่าเพื่อการศึกษาโดยได้รับบริจาคจาก คณะครู  คณะกรรมการสถานศึกษา ผู้ปกครองนักเรียน และศิษย์เก่า โดยสามารถจัดหาคอมพิวเตอร์ได้ทั้งหมด 13 เครื่อง มูลค่า 172,229 บาท รวมทั้งได้รับการบริจาคโทรทัศน์พร้อมเครื่องเล่นดีวีดี จำนวน 1 ชุด มูลค่า 9,000 บาท จากศิษย์เก่า

                   พ.ศ. 2550 – 2551 ได้ปรับปรุงอาคารเรียน ใช้งบประมาณ 50,000 บาท และทำรั้งด้านหน้าโรงเรียน ใช้งบประมาณ 3,000 บาท

                   พ.ศ. 2551 – 2552 ได้สร้างเสาธงโดยได้รบความช่วยเหลือจากคณะครู นักการภารโรง คณะกรรมการสถานศึกษา ผู้ปกครอง เป็นจำนวนเงิน 30,000 บาท

                   ปัจจุบัน โรงเรียนบ้านผือฮีนาลานาจาน ได้เปิดทำการสอนระดับปฐมวัย และประถมศึกษา มีจำนวนนักเรียนทั้งหมด 40 คน มีทั้งหมด 8 ห้องเรียน