Walter Kleeblatt wurde als Sohn von Solomon Kleeblatt und Helene Alexander in Salder, heute ein Teil von Salzgitter, Niedersachsen, geboren. Er hatte zwei Geschwister: Arthur (geb. 1896) und Edith (geb. 1907, verheiratet mit Walter Hirsch). Die Familie besaß ein Textilgeschäft, das Solomon gemeinsam mit Helene’s Bruder Isaak Alexander gründete. Nach dem Tod von Solomon 1917 und Isaak 1918 musste Helene das Geschäft mit Unterstützung ihres Neffen Julius Gutheim führen. Später übernahmen Walter und Julius gemeinsam die Geschäftsführung.

Walter verlobte sich im Mai 1932 mit Gretel David aus Wolfenbüttel, und die beiden heirateten am 14. Januar 1934; die Trauung vollzog der Bochumer Rabbi Moritz David. Durch die Boykotte jüdischer Geschäfte musste die Familie 1935 ihr Geschäft schließen und nach Hannover ziehen, wo Walter in einer jüdischen Bäckerei arbeitete.

1937 erhielten Walter und Gretel US-Visa, und im Februar 1938 reisten sie mit dem Passagierschiff SS Manhattan nach Amerika. Sie hofften, dass Walters Schwester Edith, deren Mann Walter Hirsch und deren Sohn Werner nachkommen würden. Ediths Familie floh 1939 illegal nach Belgien, doch Walter Hirsch wurde nach der deutschen Besetzung in verschiedene Internierungslager deportiert und starb schließlich in Auschwitz. Edith, bereits an Krebs erkrankt, starb 1941, und ihr Sohn Werner überlebte unter falscher Identität.

Während des Holocausts wurden auch Walters Mutter Helene und Bruder Arthur deportiert; Helene starb in Theresienstadt, Arthur in Auschwitz. Nach dem Krieg gelang es Walter und Gretel, ihren Neffen Werner über die Hilfe des Roten Kreuzes in die USA zu bringen. Von der erweiterten Familie Kleeblatt überlebten neben Walter und Gretel nur Werner die Shoah.