In alten Chroniken wird das heutige Walle unter der Ortsbezeichnung Scheverlingenburg erstmals gegen Ende des 11. Jahrhunderts erwähnt: Um 1090/91 wird Braunschweig durch feindliche Truppen des Kaisers Heinrich IV besetzt. Die damalige Braunschweiger Markgräfin Gertrud entzieht sich der Besatzung durch Flucht auf die Scheverlingenburg, eine auf einem Plateau zwischen den Flüssen Schunter und Oker befestigte Anlage, die zu der Zeit im Besitz der Brunonen war. Deren Erdwällen verdankt Walle vermutlich seinen Namen. Seine größte Bedeutung erfährt der Ort unter Kaiser Otto IV, dessen Aufenthalt am 10. Juni 1212 durch eine von ihm an diesem Tage in Keverlingenburg ausgestellte Urkunde bezeugt ist. Im Januar 1213 gründet er dort eine Kirche und stattet sie mit zahlreichen Privilegien und Ländereien aus, so auch die nördlich von Veltenhof an der Oker gelegeneSiedlung Honrode. Der Umfang dieser Stiftung gab Historikern Anlass zu der Vermutung, dass hier ein Kloster oder spätere Grabeskirche entstehen sollte. Der Reichsapfel im Waller Wappen erinnert an diesen geschichtlichen Hintergrund.
Otto stirbt am 19. Mai 1218 auf der Harzburg. In dem Testament vom Vorabend seines Todes überträgt er Scheverlingenburg samt Kirche und deren Besitztümern auf das Stift St. Blasius mit dem Braunschweiger Dom als Stiftskirche.
Der Ortsname Walle läßt sich zum ersten Mal in einer Urkunde aus dem Jahr 1406 nachweisen. Scheverlingenburg gerät danach allmählich in Vergessenheit.
Niedersächsisches Amt für Denkmalpflege: Archäologisches Kulturdenkmal Burg mit geschützter Fläche. Lageplan im Verzeichnis der Kulturdenkmale.
Kaiser Otto IV
Otto IV von Braunschweig war von 1198 bis 1208 zunächst römisch-deutscher König und ab 1209 dann auch Kaiser des römisch-deutschen Reichs.
Geboren wurde er 1175 oder 1176 wahrscheinlich in Braunschweig als Sohn von Heinrich dem Löwen und Mathilde Plantagenet aus dem englischen Königshaus. Otto lebte etliche Jahre im Exil in England. Unter anderem belehnte ihn dort sein berühmter Onkel Richard Löwenherz mit der Grafschaft York .
Otto starb am 19. Mai 1218 auf der Harzburg.