Paul von Zsolnay was born in Budapest in 1895 as the first son of the tobacco industrialist and Austrian consul general Adolf von Zsolnay (1866–1932) and his wife Klara Amanda, called Andy (1876–1956), née Wallerstein. His brother Friedrich (Fritz) was born just under a year later in Bad Ischl. The family left the Jewish community in 1901 and joined the Augsburg Confession. After studying agriculture at the University of Natural Resources in Vienna, he managed the family's property in Oberufer near Pressburg, which thanks to his mother was a popular meeting place for artists and intellectuals. Inspired by these surroundings and with the financial support of his parents, in 1923 he founded Paul Zsolnay Verlag at Prinz Eugen-Straße 30 in Vienna's 4th district. In 1929 he married the sculptor Anna Mahler (1904–1988) secretly in Paris. The couple moved to Maxingstraße 24 in the 13th district, called the Kaunitzschlössel, which was also the home of a literary salon. Daughter Alma was born on 5 October 1930, and that year Paul Zsolnay moved briefly to Berlin. In 1935 the couple divorced. Alma lived with her father and widowed grandmother Andy. Adolf Zsolnay had died in 1932 and bequeathed one quarter of his collection of classical art to his wife and three-eighths each to his sons Paul and Fritz. A collection of Coptic textiles that Adolf Zsolnay had given to the Egyptian and Near Eastern Collection of the Kunsthistorisches Museum (KHM) in Vienna for safekeeping in 1931 remained there after his death.

The asset declarations that Paul and Andy Zsolnay were obliged to make in July 1938 valued Paul Zsolnay's share of the art collection, comprising stone figures, heads, statues, reliefs, jewellery and coins, at around 10,000 Reichsmarks, and his mother's jewellery and art objects at around 57,000 Reichsmarks. In autumn 1938 Paul Zsolnay fled to London, and his mother and daughter followed, detouring through Czechoslovakia, in early 1939. After a short period of detention, his brother Fritz Zsolnay had left Reich German territory by agreement with the Gestapo on 21 March 1938 and fled initially with his family to Budapest and from there to Switzerland and then to Britain. On 14 November 1938 Andy and Paul Zsolnay applied to export to Hungary twenty-four carpets, forty-eight classical figures and reliefs, and nine paintings, which were stored with Spedition Caro & Jellinek in Vienna. The Zentralstelle für Denkmalschutz (Central Monument Protection Office) ordered in May and June 1939 the securing by Vienna municipal department 50 of two classical eave mouldings, a grave relief and a panel from the removal container and later also the artworks and furnishings remaining in the villa, which were subsequently put up for sale at the end of 1939 by Bernhard Witke, appointed as trustee by the Vermögensverkehrsstelle (Property Transaction Office). In 1940 the KHM acquired around twenty objects from the Zsolnay collection and inventoried them in the Collection of Greek and Roman Antiquities and in the Egyptian and the Near Eastern Collection. Books and manuscripts went to the National Library, while other objects transferred to Baldur von Schirach and intended for the Kunstmuseum Linz were sold through the Dorotheum or remained in the monuments office depot.

After the war, Paul Zsolnay returned to Vienna to recover his publishing company, which had been Aryanized in June 1938 by the former writer for the company Albert Jantsch-Streerbach with NSDAP member Hannes Dietl on the basis of an oral agreement between Zsolnay and Jantsch-Streerbach. Zsolnay commuted in subsequent years between London and Vienna. In 1947/48 Paul, Fritz and Andy Zsolnay applied for restitution of the art collection dispersed in Munich, Altaussee and Vienna. Parallel to the restitution proceedings, the KHM attempted to acquire the grave relief and the two eave mouldings for the Collection of Greek and Roman Antiques, and to keep one of the Coptic textiles in return for having kept it in custody for so many years. The Egyptian and the Near Eastern Collection did indeed obtain a linen item with figurative insert as a gift in 1948. The following year, 233 Greek, 26 Roman and 28 other coins, two scarabs, a number of ornaments, a Madonna and Child panel painting and some original manuscripts were returned to London. The three classical objects that had been removed from the export authorization were purchased by the KHM in 1951. In view of the material and temporal connection between the acquisition of the objects to be restituted and the Export Prohibition Law, the Art Restitution Advisory Board recommended in 2014 that the grave relief and the two eave mouldings but not the Coptic textiles be returned by the KHM to the legal successors of Andy, Friedrich and Paul Zsolnay.