Around 1973, West German security organizations received information that one of Brandt's personal assistants, Günter Guillaume, was a spy for the East German state. Brandt was asked to continue work as usual, and he agreed, even taking a private vacation with Guillaume. Guillaume was arrested on April 24, 1974. For some reason, the West German government blamed Brandt for having a spy in his party. At the same time, some revelations about Brandt's private life (he had had some short-lived affairs with prostitutes) appeared in newspapers. Brandt contemplated suicide and even drafted a suicide note. But he lived on, accepted responsibility, and resigned on May 7, 1974.
Guillaume had been a spy for East Germany, supervised by Markus Wolf, head of the Main Intelligence Administration of the East German Ministry for State Security. Wolf stated after German reunification that the resignation of Brandt had never been intended, and that the affair had been one of the biggest mistakes of the East German secret service.
Brandt was succeeded as Chancellor by the Social Democrat Helmut Schmidt, who unlike Brandt belonged to the right wing of his party. For the rest of his life, Brandt remained suspicious that his fellow Social Democrat and longtime rival Herbert Wehner had been scheming for his downfall, but evidence for this seems scant.
Aside from internecine intrigue within the Social Democrats, the finger of blame for Brandt's fall was also pointed at the East German leadership. Some speculated that the East German regime under Erich Honecker had intentionally used Guillaume to engineer Brandt's downfall. Brandt's policy of Ostpolitik had made him a hero and symbol of hope for national and family reunification in the East. Therefore, from Honecker's view, Brandt's popularity in East Germany represented a threat to the regime. In his memoirs, Brandt noted Honecker's denial of complicity in his downfall, adding "whatever one may think of that." (Brandt, My Life)
Guillaume was eventually released to the East German regime in 1981 in return for Western intelligence agents caught by the Eastern Bloc. Back in East Germany, Guillaume was celebrated as a hero, worked in the training of spies, and published his autobiography Die Aussage (The Statement) in 1988.
The story of Brandt and Guillaume is told in the play Democracy (play) by Michael Frayn. The play follows Brandt's career from his election to Guillaume's imprisonment. It examines Guillaume's dual identity as trusted personal assistant to the West German chancellor and Stasi spy, and his conflict as his duty to Brandt's enemies clashes with his genuine love and admiration for the chancellor.