Die Burg wurde wahrscheinlich um die Mitte des 13. Jahrhunderts von Albert I. von Wallenstein (vormals Graf von Schauenburg) erbaut, der seit Anfang des Jahrhunderts auf der sechs Kilometer nordwestlich gelegenen Burgruine Wallenstein („Waldinsteyn“) residiert hatte und nach der er sich seit 1233 auch nannte. Beide Burgen lagen an der Straße von Hersfeld über Homberg (Efze) und Fritzlar nach Kassel.

Die Burg wurde erstmals 1267 als „Neuwallenstein“ erwähnt, als Albert II. von Wallenstein mit dem Hersfeld Abt einen Tauschvertrag abschloss. Conrad von Wallenstein, vermutlich ein Bruder von Albert I., trat das Erbe von Albert II. an, als dieser 1284 starb. Conrad wurde damit zum Begründer der neuen Wallensteiner Linie. Er führte keinen Grafentitel mehr, da aller Wahrscheinlichkeit nach wohl schon seine Schauenburger Vorfahren das Obergericht Ditmold (mit dem der Grafentitel verbunden war) in der ersten Hälfte des 13. Jahrhunderts an das Erzbistum Meinz verkauft hatten.

Im 14. Jahrhundert gehörte Simon von Wallenstein noch eine Hälfte der Burg. Die andere Hälfte teilten sich Friedrich von Schlitz (genannt von Steinau) und Friedrich von Herzberg. Um den Straßenräubereien der Wallensteiner ein Ende zu machen, verbündete sich ihr Lehnsherr, der Hersfelder Abt Simon I. von Buchenau, mit Landgraf Otto I von Hessen, Graf Johann I von Ziegenhain und dem Landfriedensrichter und Reichslnadvogt in der Wetterau , Eberhard von Breuberg.

Am 24. Juli 1318 zerstörten sie gemeinsam das Raubritternest Neuwallenstein. Erst 1357, als Simon von Wallenstein sich mit seinem neuen Lehnsherrn Otto I. von Hessen gegen die Kloster Fulder verbündete, erhielt er die Erlaubnis, die Burg wieder aufzubauen.

Im Jahre 1521 starb die albertinische Linie der Wallensteiner aus und es kam zu jahrelangen Erbstreitigkeiten, wobei die Burg oft ihre Besitzer wechselte. Was mit der Burg im Dreißigjährigen Krieg geschah, ist nicht bekannt. Ab 1639 bis 1643 erfolgte ein Umbau der Burg, wobei der Palas schlossartig erneuert wurde.

Nach dem Tod von August Gottfried Freiherr von Wallenstein, dem letzten Wallensteiner, im Jahr 1745 fiel die Burg als erledigtes Lehen an Hessen-Kassel zurück. Die Verteidigungsanlagen wurden abgerissen, und nur der 28 Meter hohe Bergfried, mit bis zu zwei Meter dicken Mauern, blieb bis heute erhalten. Das Schloss wurde dann als landgräflicher Jagdsitz verwendet. Ab 1775 war es Sitz des Amtes Obergeis und von 1760 bis 1866 Sitz eines hessischen Domänenrentmeisters. Zwei Gebäude der ehemaligen Rittergut ( Domäne) stehen noch nordwestlich des Schlosses, am gegenüberliegenden Hang. Ab 1870 zog ein preußisches, ab 1919 hessisches Forstamt ein. Das Forstamt Neuenstein blieb bis zu seiner Auflösung 1997 in den Räumen des Schlosses.

Die Gemeinde Neuenstein kaufte das Schloss im Jahre 2000 und baute es 2002 bis 2003 zu einem Tagungs- und Veranstaltungszentrum um.