Na zwolnienie z radzieckiej niewoli Paulus musiał czekać do 1953 roku. We wrześniu tego roku do ZSRR przybył przewodniczący Rady Państwa NRD Walter Ulbricht celem omówienia zwolnienia feldmarszałka, zaś 26 października Paulus przyjechał pociągiem do Berlina Wschodniego. Na miejscu został zabrany na oficjalne przyjęcie kierownictwa państwowego i partyjnego NRD. Delegacji przewodniczył Arno von Lenski, jeden z generałów 6 Armii, po wojnie pełniący funkcję dowódcy wojsk pancernych w Kasernierte Volkspolizei. Jako miejsce zamieszkania Paulusowi przydzielono willę w drezdeńskiej dzielnicy Oberloschwitz. Otrzymał także przywilej posiadania własnej broni krótkiej i zachodnioniemieckiego samochodu Opel Kapitän. W NRD Paulus pozostawał pod pełną obserwacją Państwowej Służby Bezpieczeństwa, jego korespondencja pocztowa była sprawdzana, zaś telefon i miejsce zamieszkania podsłuchiwane.
Krótko po przyjeździe Paulusa do NRD prasa w RFN spekulowała, czy feldmarszałek będzie uczestniczyć w tworzeniu wojsk lądowych NRD, które wówczas funkcjonowały zakamuflowane jako Kasernierte Volkspolizei (KVP;