În timpul administrației turcești, Prefectura Constanța sau Kiustenge, funcționa pe locul unde astăzi exista Liceul „Mihai Eminescu”. Tot în acest conac s-a instalat și primul prefect roman al Constanței, Remus Opreanu, în anul 1878, după ce Dobrogea a fost alipită Regatului roman, ca urmare a Războiului de Independență. În anul 1882, conacul moștenit de la turci a fost mistuit de un incendiu. Rămasă fără prefectură, administrația românească a început să-și pună problema construirii unui sediu adecvat pentru ridicarea unui Palat Administrativ la Constanța, astăzi sediul Cercului Militar.
Primele eforturi concrete în acest sens s-au făcut însă abia în anul 1892, după ce timp de 10 ani prefectul și echipa lui s-au tot mutat dintr-un sediu în altul.
Proiectul a fost schimbat de 3 ori, de data aceasta fiind angajat un nou arhitect, Daniel Renard, cel care tot în 1903 avea să primească și comanda Cazinoului constănțean. Daniel Renard și-a lăsat amprenta în special asupra interioarelor unde s-a străduit să creeze ambianța „la belle epoqhe„. Cu totul remarcabilă este scara interioară, monumentală și eleganță. De remarcat că multe dintre elemente arhitectonice care decorează interiorul Palatului Administrativ, astăzi sediul Cercului Militar, pot fi observate și în sălile Cazinoului constănțean.
La 17 august 1903, în prezența ministrului Dimitrie Sturza și a altor numeroase personalități atât locale, cât și din capitală, s-a pus piatra de temelie a Palatului Administrativ. Tot în aceeași zi, oficialitățile prezente au celebrat și începerea lucrărilor la primul bulevard al orașului, bulevardul Elisabeta.
Ca orice eveniment important și inaugurarea Palatului Administrativ a fost celebrată printr-un fastuos banchet ce s-a desfășurat la bordul vaporului „Principesa Maria„. Presa locală nu a omis să relateze nici cele mai mici amănunte legate de acest elegant banchet organizat de prefectul Virnav. Aflăm astfel lista completa a celor 54 de invitați, toasturile ținute de primul ministru Sturza, prefect, primar, lista completă a meniului, scrisă integral în franceză, faptul că oaspeții s-au distrat în acordurile orchestrei Dinicu și ca vaporul luminat feeric. De asemenea, aflăm că petrecerea a costat 1.219,22 lei, o sumă considerabilă pentru anul 1903, care a fost achitată de primărie deoarece banchetul a fost oferit de comuna Constanța.
La 1 februarie 1906 a fost facuta receptia definitiva a cladirii, de catre o comisie special desemnata, comisie care a constatat multe defecte de construcție, precum: crăpături în pereți, tâmplărie imperfectă, vopsea cojită și căzută, geamuri fără chit, parchet rău așezat, trepte nefinisate la scara de onoare, canalizare proastă și alte asemenea defecte. Poate că membrii comisiei au exagerat. Într-o anumită măsură însă se poate spune ca au avut dreptate, deoarece clădirea a necesitat multe reparații de-a lungul timpului, dovedindu-se destul de șubredă. Evident, în spiritul timpului, mai criticat decât clădirea a fost prefectul Scarlat Virnav, acuzat că a început toate lucrările edilitare pentru a jongla cu banii publici în interes propriu. Nici arhitectul Daniel Renard nu a scăpat criticilor.
