In the aftermath of the Second World War, the search for alleged traitors took place in each country that had been under foreign occupation. The most active country in this regard was the Soviet Union. This article analyzes how the Soviet authorities dealt with people who had lived in German-occupied territory during the war. It discusses divergent understandings of guilt, and examines means of punishment, retribution and justice. I argue that inconsistencies in Moscow’s politics of retribution, apart from reflecting tensions between ideology and pragmatism, resulted from contradictions within ideology, namely the belief that the war had uncovered mass enemies in hiding, and the belief that it had been won with the mass support of the Soviet population. The state that emerged from the war, then, was both powerful and insecure, able to quickly reassert its authority in formerly German-occupied areas, but also deeply ambivalent about its politics of retribution.