De andere zijde van Pauls jonge leven wordt gekenmerkt door antisemitisme van Roemeense, Russische en Duitse zijde. Tot driemaal toe wordt hij gedwongen van school of opleiding te wisselen. Want ook in Roemenië zijn er rechtse groeperingen die anti-Joods zijn, zoals Paul tijdens zijn schooltijd ervaart. In een brief aan zijn naar Palestina gevluchte tante Minna schrijft hij dat hij een 300 bladzijden dik boek zou kunnen schrijven over het antisemitisme in zijn klas. Meerdere keren heeft hij conflicten met leraren. Klasgenoten herinneren zich dat Paul telkens weer met antisemitische docenten in debat gaat om de Duits-joodse cultuur en de Jiddische taal te verdedigen, al spreken zijn ouders en hij thuis geen Jiddisch, maar Duits.

Na het uitbreken van de Tweede Wereldoorlog wordt het gebied op grond van het pact tussen Hitler en Stalin op 20 juni 1940 door het Russische leger bezet. Joden die verdacht worden van zionistische activiteiten worden gedeporteerd naar Siberië. Paul moet meewerken aan de verspreiding van marxistisch-leninistische propaganda, bijvoorbeeld bij de viering van 1 mei (de internationale Dag van de Arbeid). In zijn strijd tegen het antisemitisme heeft Paul weliswaar linkse sympathieën, maar hij wantrouwt de Russen. Uit de berichten van de Franse schrijver André Gide weet hij dat Stalin in de jaren 1930 in de Sovjet-Unie duizenden joden heeft laten vermoorden.

Op 5 juli 1941 bezetten Duitse nazitroepen Czernowitz. Meer dan 3000 vooraanstaande joden worden vermoord en meer dan 45.000 mensen worden gedwongen in een getto te leven. Paul wordt ingezet bij het inzamelen en verbranden van communistische boeken en pamfletten. Wanneer de deportaties van joden beginnen duikt hij - zo wordt later bericht - regelmatig onder in een oud fabriekspand of logeert hij bij een vriendin. Zijn ouders duiken niet onder, hopen wellicht dat de transporten hen naar een voor Joden bestemd ‘vrij gebied’ zullen brengen. Voor het plan van zijn vader om naar Israël te vluchten, is het dan al te laat. Op zaterdag 12 juni 1942 worden de ouders opgepakt en door de nazi’s naar het concentratiekamp Michailovka gedeporteerd. Pauls vader sterft enkele maanden later aan tyfus en zijn moeder wordt kort daarop door een nekschot vermoord.

Paul heeft de Roemeense nationaliteit en moet zich net als alle mannen tussen 18 en 48 jaar melden voor tewerkstelling. Hij zit van juni 1942 tot februari 1944 gevangen als dwangarbeider, de eerste drie maanden ondergebracht in een huis, later in meerdere werkkampen. Het zijn vaak mobiele kampen, waar de gevangenen in de open lucht overnachten. Gedurende de dag moeten ze puin ruimen, stenen sjouwen of greppels graven (‘schaufeln’) voor de aanleg van wegen en bruggen. Het eten is slecht, vaak niet meer dan waterige soep. In de kampen leert hij Jiddisch spreken en maakt kennis met Joden uit geheel andere milieus. Tijdens zijn gevangenschap heeft Paul soms even contact met vrienden, van wie hij hoort dat zijn ouders zijn vermoord. Over de dood van zijn vader bericht zijn moeder hem waarschijnlijk in een uit het kamp gesmokkelde brief, en van zijn uit het kamp gevluchte neef hoort hij later dat zijn moeder eind 1943 is vermoord. Omdat contact soms mogelijk is kan hij aan zijn vriendin Ruth Lackner ook in gevangenschap geschreven gedichten meegeven, in de hoop dat ze bewaard blijven. In februari 1944 wordt Celan vrijgelaten uit het werkkamp en keert terug naar huis. Eind maart nemen de Russen de Boekovina in bezit. In de daarop volgende maanden wordt langzaam duidelijk welke verschrikkingen de nazi’s hebben aangericht. Paul hoort verhalen van overlevenden en leest in Russische kranten als Izvestia berichten over de moordpartijen en massagraven in het getto van Lemberg (het huidige Lviv; bericht  in Izvestia van 23 december 1944). Deze berichten en zijn eigen ervaringen verwerkt hij in eind 1944 in zijn gedicht 'Todestango', dat hij kort daarop Todesfuge noemt. Later dateert Celan het ontstaan van Todesfuge op begin mei 1945.  Hij noemt het gedicht een 'graf en een grafschrift' en voegt toe: 'Ook mijn moeder heeft alleen dit graf'.