Palæet er opført i årene 1752 - 1755 af Geheimeråd, Greve August von Berckentin,  tegnet af hans meget gode ven, arkitekten J.G. Rosenberg, som også ledede byggeriet.  Byggeriet menes færdig i 1755,  selvom en tavle over Palæets hovedindgang viser året 1753.
Efter Grev Berckentin død, den 2. juli 1758, overgik palæet til hans datter Louise von Plessen som dog ikke ønskede at bebo palæet, men istedet udlejede det, først i en kortere periode til baron von Steinberg, og fra 16. oktober 1761 til Heinrich Carl Schimmelmann, tysk forretningsmand og mangemillionær. Med hans lejekontrakt fulgte en forkøbsret, idet han, hvis han ønskede det, kunne købe Palæet med inventar for 40.000 rigsdaler, en forkøbsret han benyttede sig af efter en kort årrække. 
Efter Heinrich Carl Schimmelmann død i 1782 overtog sønnen Heinrich Ernst Schimmelmann palæet som blev i familiens eje i yderligere 4 generationer.
I 1884 solgte den sidste efterkommer af Heinrich Carl Schimmelmann palæet til Aktieselskabet Koncertpalæet for 450.000 kr.. Efter overtagelsen gik selskabet igang med en større ombygning, herunder opførelsen af en stor koncertsal som stod færdig og indviedes den 2. november 1889. I de følgende år blev både den lille og den store koncertsal ramme om alt, hvad der var førende inden for koncerter i hele nordeuropa.
Økonomien stod ikke mål med de store anstrengelser, for som der står "Kun garderoben giver overskud", så på en generalforsamling 17. august 1900 vedtoges det at sælge Koncertpalæet til de københavnske Odd Fellow Loger under den uafhængige storloge for kongeriget Danmark I.O.O.F. for en pris af 1.020.000 kr.. Ved overtagelsen 30. august 1900  ændrede palæet navn fra Koncertpalæet til Odd Fellow Palæet.

De loger og lejre som sammen med storlogen købte palæet i 1900 var:  Loge nr. 1, Danmark -  Loge nr. 2, Scandinavia  -  Loge nr. 3, Nordstjernen  -  Loge nr. 6, Eureka  -  Loge nr. 11,  Columbus  -  Loge nr. 13, Venskab  -  Loge nr. 28, Hafnia  - Rebekkaloge nr. 1, Caroline Amalie samt Lejr nr. 1 Valdemar og Lejr nr. 2 Knud Lavard.