The name was given to the mill by Christian A. Gersdorff, the Baron of Marselisborg Manor, who had served as a general in the army of the Russian Tsar on the Black Sea coast.

Both names refer to cities in modern northeastern Bulgaria, then under Ottoman rule, that were subjected to prolonged Russian sieges during the Russo-Turkish War of 1828–29.

Varna Palæet is a result of this decision and it was completed in time for the exhibition along with another pavilion, Ørnereden (English: Eagles Nest).

In the first years the Varna Soiré (Varna-Soiréen) started in 1913 was the best known tradition featuring known actors, musicians, cabaret- and opera singers and poetry recitals.

The venue continued being popular and in 1936 some 20.000 people attended the summer "solstice" celebrations with entertainment by orchestras, tango-contests, gypsies and operetta.

The classical decorations were removed in favor of psychedelic patterns in aubergine, orange, red and purple and furniture in steel and plastic.

The final plans were accepted by the city council on 16 January 1908 and Eggert Achen quickly began construction so the building could be completed for the opening of the National Exhibition in May 1909.