Το Νεοχώρι άρχισε να κτίζεται μετά την τουρκική εισβολή από τέσσερις οικογένειες κτηνοτρόφων που απέμειναν στην περιοχή. Αυτές καθόρισαν τα όρια του χωριού αφού τα σπίτια τους ήταν σε 4 σημεία, που όριζαν τα άκρα ενός νοητού σταυρού. Ο νέος οικισμός δημιουργήθηκε περίπου το 1600 από κατοίκους που προέρχονταν από τη Βυζαντινή Πόλη Λάη, σε απόσταση 3 χιλιόμετρα από το σημερινό Νεοχώρι. Για την ονομασία του χωριού Νεοχώρι υπάρχουν δύο εκδοχές: η πρώτη υποστηρίζει ότι ονομάστηκε έτσι επειδή ήταν το νεότερο χωριό από τους κτηνοτροφικούς οικισμούς που υπήρχαν στην περιοχή μέχρι τότε. Αντίθετα, η δεύτερη εκδοχή στηρίζει ότι θα μπορούσε το όνομα να είναι εξελληνισμός του Νιαχώρι που σημαίνει Μανδροχώρι