Las negociaciones entre Brandt y el jefe de gobierno de la Alemania del Este, Willi Stoph, empezaron rápidamente, pero no fue posible llegar a un acuerdo formal, ya que Brandt no estaba dispuesto a reconocer la parte oriental como un Estado soberano, aun cuando la RDA estaba dispuesta a aceptar la fórmula que "Alemania era una sola nación pero con dos Estados".