The story begins in Nazi Germany in April 1964, in the week leading up to Adolf Hitler's 75th birthday. The plot follows detective Xavier March, an investigator working for the Kriminalpolizei ( Kripo ), as he investigates the suspicious death of a high-ranking Nazi, Josef Bühler, in the Havel on the outskirts of Berlin. As March uncovers more details, he realises that he is caught up in a political scandal involving senior Nazi Party officials, who are apparently being systematically murdered under staged circumstances. As soon as the body is identified, the Gestapoclaims jurisdiction and orders the Kripo to close its investigation.
March meets with Charlotte 'Charlie' Maguire, a female American journalist also determined to investigate the case. They both travel to Zürich to investigate the private Swiss bank account of one of the murdered officials. Ultimately, the two uncover the truth behind the staged murders: Reinhard Heydrich, the head of the SS, has ordered the Gestapo to eliminate the remaining officials who planned the Final Solution (of which few Germans are aware) at the Wannsee Conference in January 1942. The elimination is being hurried to safeguard an upcoming meeting of Hitler and United States President Joseph P. Kennedy by ensuring that the fate of Europe's Jews can never be revealed. Maguire heads for neutral Switzerland, hoping to expose the evidence of the extermination to the world. March, however, is denounced by his ten-year-old son and apprehended by the Gestapo.
In the cellars of Gestapo headquarters at Prinz-Albrecht-Straße, March is tortured but does not reveal the location of Maguire. Globocnik boasts that Auschwitz and the other camps have been totally razed, and March will never know the truth for certain. Kripo Chief Arthur Nebe stages a rescue, intending to track March as he meets with Maguire at their rendezvous in Waldshut-Tiengen on the Swiss/German border. March realises what is happening and heads for Auschwitz, leading the authorities in the wrong direction.
The Gestapo catches up with March at the unmarked site of Auschwitz. Knowing that Maguire has had the time to cross the border into Switzerland, March searches for some sign that the camp existed. As Gestapo agents close in on him in a helicopter, March uncovers bricks in the undergrowth. Satisfied, he pulls out his gun and leaves the reader to draw their own conclusions.
British scholar Nancy Browne noted the similarities between the ending of "Fatherland" and that of Ernest Hemingway's "For Whom the Bell Tolls": "Both novels end with the protagonist about to embark on a single-handed armed confrontation with a large number of Fascists or Nazis, of whose outcome there can be no doubt - but the reader does not witness the moment of his presumed death.(...) Like Hemingway's Robert Jordan, Xavier March is facing this last moment with an exhilaration born of having no further doubts and dilemmas, no more crucial decisions which need to be made, nothing but going through on his chosen course and dying in a just cause. And like Jordan, in sacrificing himself March is ensuring the safe escape of the woman he loves.