Paula Wolf was een van de zeven kinderen van Leopold Isaac en Olga Gumpel. Het gezin Isaac veranderde in 1924 de naam naar Wolf. De reden hiervoor was dat Leopold lid was van de "Gebroeders Wolf", een populair vaudeville gezelschap uit Hamburg. De familie was tevens in het bezit van meerdere theaters in dezelfde stad.
Na het huwelijk van Paula met Fritz Stern, ging het echtpaar in 1938 wonen in …