Mittelalter bis Neuzeit
Wallstawe hat auf den Urmesstischblatt 1823 die Form eines Straßenangerdorfs mit Kirche, war aber ursprünglich rund gebaut (Rundling).
Im Jahre 1251 wird Bodo de Walstawen in Salzwedel erwähnt.
Die erste urkundliche Erwähnung von Wallstawe stammt aus dem Jahre 1306, als Burchard von Wallstawe in walstawe seine Schenkung an das Kloster Diesdorf beurkundet. Das Adelsgeschlecht von Wallstawe wohnte bis ins 14. Jahrhundert in Wallstawe.
Im Landbuch der Mark Brandenburg von 1375 wird der Ort als Valstove und als Walstove aufgeführt. Später ging der gesamte Besitz der von Wallstawe an die von der Schulenburg zu Beetzendorf und Apenburg über.
Die Landeshoheit lag zunächst beim Markgrafen von Brandenburg, vor 1402 teilweise bzw. später ganz und bis 1692 beim Herzog von Braunschweig-Lüneburg. Im Jahre 1687 hieß es: „Ist nicht märkisch, auch nicht lüneburgisch, steht im Streit, wird dahero mit keiner Kontribution belegt, sind also freie Leute.“
Mit dem Vertrag von Wallstawe von 1692 kam Wallstawe als ehemalige lüneburgische Exklave im Kurfürstentum Brandenburg an Brandenburg.
1823 wurde das Dorf durch einen großen Brand verwüstet.
Noch in der Mitte des 20. Jahrhunderts waren zwei Mühlen an der Beeke in den Mühlenwiesen nördlich des Dorfes auf dem Messtischblatt verzeichnet, eine Wassermühle am Nordende des Dorfes (Wallstawer Mühle) und eine Windmühle weiter im Norden.
Im Jahre 1954 entstand die erste Landwirtschaftliche Produktionsgenossenschaft vom Typ III, die LPG „IV. Parteitag“.
Eingemeindungen
Wallstawe gehörte ursprünglich zum Salzwedelischen Kreis der Mark Brandenburg in der Altmark. Von 1807 bis 1813 lag es im Stadtkanton Salzwedel auf dem Territorium des napoleonischen Königreichs Westphalen. Nach weiteren Änderungen kam es 1816 in den Kreis Salzwedel, den späteren Landkreis Salzwedel im Regierungsbezirk Magdeburg in der Provinz Sachsen in Preußen.
Die Gemeinde Wallstawe wurde am 25. Juli 1952 in den Kreis Salzwedel umgegliedert. Am 1. Juli 1994 kam sie zum Altmarkkreis Salzwedel. Durch einen Gebietsänderungsvertrag beschlossen die Gemeinderäte der Gemeinden Gieseritz (am 18. November 2008), Wallstawe (am 19. November 2008) und Ellenberg (am 20. November 2008), dass ihre Gemeinden aufgelöst und zu einer neuen Gemeinde mit dem Namen Wallstawe vereinigt werden. Dieser Vertrag wurde vom Landkreis als unterer Kommunalaufsichtsbehörde genehmigt und trat am 1. Juli 2009 in Kraft.
