Сградата, в която днес се помещава Държавният архив, е най-старата административна сграда във Варна и има над 100-годишна история. Построена през 1860 г., днес тя е една от малкото стойностни архитектурни сгради от преди Освобождението. При строежа на сградата, която тогава е била турският конак, е разрушена част от гробница, намираща се пред входа на архива.

Главната фасада на архива е разчленена от ризалит, поставен симетрично на централната й ос. Долната част от ризалита е зает от балдахинов вход, изграден от четири правоъгълни колони. Над входа е поставен заоблен балкон, носен от две декоративно оформени конзоли. Фасадата на ризалита завършва с фронтон, в който е поставен гербът на републиката и фланширан с две декоративни вази. Прозорците на всички фасади са леко засводени и обрамчени с каменни рамки с малък перваз.

След Освобождението първоначално сградата служи за седалище на губернатора. Освен това тук се помещават почти всички държавни учреждения. В две от стаите през 1885 г. се помещава дори БНБ. Когато се премахва институцията на губернаторите и се създават окръжните управления, тук се настаняват Окръжното управление и другите служби.

Сградата винаги е била държавна. До 1944 г. в нея се помещава и полицейското управление. През 1990 г., когато Държавният архив получава сградата, в продължение на 5 години се извършва реконструкция. Тъй като тя е паметник на културата и архитектурата, външният й облик не може да бъде променян.

Днес сградата е паметник на архитектурата от местно значение, а декоративното осветление нощем й придава допълнителен чар.