The paper characterises the several-decades-long process of rehabilitation of the prewar cultural heritage in the Kaliningrad. After the northern part of the former East Prussia (Königsberg, and since 1946, the Kaliningrad Oblast) had been annexed by the USSR, and after basically a total change of the population had taken place, the authorities started to Sovietise the region. Knowledge of the prewar past was prohibited from the very beginning, and Stalin-era propaganda formed the founding myth of the Kaliningrad region with reference to the notion of ‘a Slavic land from time immemorial’. Despite the significant shifts that took place in the process of research into the history of the Kaliningrad Oblast during the Soviet period, carried out by historians from Russia and other countries, the adaptation by the postwar settlers to the socio-cultural landscape remains a poorly researched theme. The paper argues that the rehabilitation of the prewar (and primarily German) cultural heritage took place all through the Soviet era, by gradually converting the initially alien environment into their own. Ultimately, a fundamental shift took place in the cultural memory of Kaliningrad’s inhabitants; from the fear of staying ‘in an empty land’, they moved to the compatibility of ‘memory and desire’: the understanding that the metaphor of ‘paradise lost’, which revealed the nostalgia of the former inhabitants of East Prussia, also defined the feelings of Kaliningrad residents for the land that had become their home.