Walter Scharfenberg wurde am 19. Februar 1932 in Charkow, der damaligen Hauptstadt der Sowjetrepublik Ukraine geboren. Seine Eltern Felicia und Nikolai hatten deutsche Vorfahren, lebten aber seit ihrer Geburt 1902 bzw. 1897 in Russland.
Am 5. Januar 1936 wurde Nikolai Scharfenberg wegen angeblich „politisch schädlicher Formulierungen“ von seinem Betrieb entlassen und in der Nacht zum 20. November 1936 von Angehörigen des NKWD verhaftet. Während seiner Haftzeit konnte der Gefangene eine Reihe von Briefen an seine Frau und seinen kleinen Sohn senden, von denen 25 überliefert sind. 1937 wurde Nikolai zu sechs Jahren Lagerhaft verurteilt und im Sommer 1938 in das Kolyma-Gebiet im fernen Osten der UdSSR deportiert.