1344 erwarb das Kloster Krevese hier Besitzungen. 1375 wird das Dorf im Landbuch Kaiser Karls IV als nathende (heide) erwähnt. Mit Heide bezeichnete man in Mittelalter eine waldlose, wildgrünende Ebene, ein unbestelltes Feld.
Natterheide gehörte schon zur Zeit Kaiser Karls IV zur Burg Krumke. Der Burgherr zu Krumke war auch Grundherr von Natterheide, damals hieß er Albert von Redern.
Das älteste Gebäude im Dorf ist die um die Mitte des 12. Jahrhunderts entstanden Kirche.
Das für die damalige Zeit moderne Schulhaus wurde 1908 erbaut. Ab 1965 gingen die Kinder nach Flessau zur Schule. Nach der Fertigstellung der neuen Schule in Flessau 1969 diente das alte Schulgebäude noch einige Jahre als Schulhort. Später wurde hier eine Konsumverkaufsstelle eingerichtet, die 1991 geschlossen wurde. Die kleinsten Natterheider wurden in den 50er Jahren im Erntekindergarten und ab den 60er Jahren in einem Dauerkindergarten untergebracht. Später mussten sie nach Flessau umziehen.
Die ehemalige Schule wird heute als Wohnhaus genutzt.
Ein weiterer Treffpunkt der Natterheider war seit 120 Jahren die Gaststätte Schulze. Hier fanden alle Versammlungen und andere Veranstaltungen statt. Handels- und Geschäftsleute aus Nattterheide und den Nachbardörfern trafen sich dort. Seit 1995 ist die Gaststätte jedoch geschlossen.
Das Dorf Natterheide ist geradlinig gebaut. Wo sich die Dorfstraße nach Späningen und Wollenrade trennt, steht die Friedenseiche. Die erste Eiche wurde hier 1870 gepflanzt. Infolge eines Blitzschlages wurde der Baum trocken und musste gefällt werden. Erneut wurde eine Friedenseiche gepflanzt. Dieser Baum wurde aber 1936 in "Hitlerseiche" umgetauft und wurde mit einer Fahnenstange und einer braunen Einzäunung versehen. Die NSDAP nutzte den Platz für Veranstaltungen. Nach Kriegsende wurde die Friedenseiche 1945 gefällt. Auf Anregung des Natterheider Bürgers Artur Schulze steht seit 1990 wieder eine Eiche auf diesem historischen Platz.
| Die 1892 gegründete Freiwillige Feuerwehr ist noch heute mit ca. 30 Mitgliedern aktiv. 1995 wurde ein neues Feuerwehrhaus gebaut. Der Gemeinschaftsraum wird für Versammlungen und Feiern genutzt. Hinter dem Haus wurden ein Grillplatz und ein großer Spielplatz gebaut. |  |
1957 vereinigten sich drei Bauern zu einer LPG vom TYP III mit dem Namen "Thomas Müntzer". Mit dem sozialistischen Frühling wurde 1960 hier die LPG TYP I "Grüne Heide" gebildet. Die lange getrennt wirtschaftlichen Betriebe schlossen sich 1970 der LPG Flessau an.
Durch Eigeninitiative der Dorfbewohner bekam Natterheide schon Ende der 60er Jahre eine Kanalisation. 1974 wurde das Dorf an die zentrale Trinkwasserversorgung angeschlossen.
1958 wurde eine Gemeindebibliothek eingerichtet. Sie steht seit Anfang der 90er Jahre, wie auch die Post und der Konsum, den Natterheidern nicht mehr zur Verfügung.
Am 01.02.1974 traten die Einwohner von Natterheide dem Gemeindeverband Flessau bei.