Nach seiner Begnadigung im Frühjahr 1956 übersiedelt Walter Kempowski in die Bundesrepublik. Sein erstes Ziel ist Hamburg, der Aufenthaltsort der Mutter, die bereits zwei Jahre zuvor aus dem DDR-Frauengefängnis Hoheneck entlassen worden war. Die Ankunft im westdeutschen Alltag missglückt zunächst gründlich: Wie schon neun Jahre zuvor bleibt die Hansestadt für Kempowski lediglich Durchgangsstation, ein Ort der Zurückweisungen und Enttäuschungen: Nach jahrelanger Haft strebt Kempowski vor allem nach öffentlicher Anerkennung für das ihm zugefügte Unrecht. Die Behandlung, die er stattdessen erfährt, stellt das genaue Gegenteil dar: Die Motive der Tat, die 1947 zur Verhaftung führten, werden nun in Zweifel gezogen. Die Tatsache, dass Kempowski 1947 gestohlene sowjetische Unterlagen in den Westen brachte, wird ihm von Vertretern der westdeutschen Entschädigungsbehörden nun als Spionagetätigkeit ausgelegt. Der Status des politisch Verfolgten, der nicht zuletzt auch für sein Selbstwertgefühl von großer Bedeutung gewesen war, wird Walter Kempowski wieder aberkannt, fortan gilt er als „gewöhnlicher Krimineller“. Bemühungen, dieses Urteil aufheben zu lassen, ziehen sich bis in das Jahr 2002 und bleiben letztlich erfolglos.
Angesichts dieser Enttäuschungen scheint es nicht verwunderlich, dass Hamburg kein dauerhafter Aufenthaltsort für Walter Kempowski werden kann. Im Frühjahr 1956 zieht er nach Göttingen, wo er zunächst das Abitur nachholt und sich dann für ein Studium an der pädagogischen Hochschule immatrikuliert. Kempowskis Ziel ist der Lehrerberuf. Neben dem Studium sind die Göttinger Jahre vor allem geprägt von dem Versuch, die Versäumnisse auf kulturellem Gebiet nachzuholen. Es kommt zu einer intensiven Beschäftigung mit Musik und Literatur. Darüber hinaus sammelt Kempowski aber auch erste Erfahrungen in der pädagogischen Praxis: Um ihn bildet sich ein Kreis von Jugendlichen, mit denen er über Bücher diskutiert und Hörspiele einstudiert. In dieser Phase nimmt darüber hinaus auch Kempowskis schriftstellerische Tätigkeit ihren Anfang, die Kernthemen seines künftigen Werks werden ausformuliert: Nachdem er bereits in Hamburg mit dem Tagebuchschreiben begonnen hatte, beginnt Kempowski nun, die Lebenserinnerungen seiner Mutter aufzuzeichnen. Aus diesen Notizen entwickelt sich bald das Projekt einer umfassenden Familienchronik, die Recherchen dehnt Kempowski über die Generation seiner Großeltern bis ins 16. Jahrhundert aus. Auf diese Weise sammelt sich über die Jahre eine gewaltige Materialfülle an. Zusätzlich zum Interesse an der Familiengeschichte trägt sich Kempowski auch mit dem Gedanken, einen Roman über seine Haftzeit zu schreiben.
Das Jahr 1960 markiert in Kempowskis Leben schließlich den endgültigen Neubeginn: Im Februar legt er an der Göttinger pädagogischen Hochschule das Erste Staatsexamen ab. Drei Monate später heiratet er die ostfriesische Pfarrerstochter Hildegard Janssen. Wenig später nimmt Walter Kempowski in der niedersächsischen Provinz seine Lehrertätigkeit auf, die Landschaft zwischen Hamburg und Bremen wird in den kommenden dreißig Jahren sein berufliches Aktionsfeld sein und auch zu seiner Heimat werden. Am Beginn von Kempowskis pädagogischer Laufbahn steht eine Volkschule in der Gemeinde Breddorf, ab 1965 unterrichtet er im nahe gelegenen Nartum, von 1974 bis 1980 schließlich in der Kleinstadt Zeven. Nartum wird schließlich auch der endgültige Wohnsitz der Familie. 1961 wird Kempowskis Sohn Karl Friedrich geboren, im Jahr darauf seine Tochter Renate.