Most previous studies on online surveillance have been conducted in long-time liberal democracies with limited experiences of explicit and intrusive state surveillance. This article explores the role of the historical legacy of totalitarianism or authoritarianism, embodied in generational experiences, in the formation of imaginaries of, and attitudes toward, contemporary state and corporate surveillance. We propose a theoretical hypothesis of the "surveillance survival paradox": firsthand experiences of the past (totalitarian/authoritarian) surveillance regime do not lead to a greater fear or criticism of the contemporary regime; rather, it is the opposite. The article presents results from an original mixed-method study combining a quantitative online survey (N=3,221) with focus group and individual interviews (seventy-one participants) conducted among two generations (born in 1946-1953 and 1988- 1995) in three European countries with different historical surveillance regimes (Estonia, Portugal, and Sweden). The quantitative analysis reveals significant cross-cultural differences in personal and mediated experiences of surveillance. Inter-generational differences in attitudes toward contemporary surveillance were surprisingly similar across the countries, with the older groups in all countries demonstrating higher tolerance toward online state surveillance, and the younger groups reporting higher acceptance for corporate dataveillance. The qualitative analysis reveals that perceptions of the past surveillance regime as more direct and dangerous overshadow sensitivities toward more abstract and covert risks related to the extended state and corporate surveillance in the contemporary datafied world. The results led us to formulate the "surveillance survival paradox" as a generation-specific, and probably also country- or regime-specific, phenomenon.