Сградата на гимназията се строи от 1893 до 1900 г. Напълно е обзаведена и открита за учебната 1898/1899 г. Строи се на мястото на бившите турски казарми. Проектът е предоставен от белгийския министър на просвещението на българския министър - варненецът Георги Живков. Архитект Петко Иванов Момчилов преработва проекта и го съобразява с местните условия.

В него е предвидена значителна паркова площ. Строежът се ръководи от арх. Христо Ковачевски от София. Представител на държавата е арх. Шрайбер, а на предприятието предприемач - Шуменското търговско дружество - арх. Сава Димитриевич.

Застрояването на сградата е симетрично, централният вход и монументалното трираменно стълбище са поставени в главната ос. Главният вход е подчертан с полукръгли арки и елегантна колонада в йонийски стил. Фасадата е с академично деление от пет части с богато архитектурно оформление на централната част. Крилата завършват с атични надвишавания. Сградата е увенчана с главен корниз, пластично обогатен с конзоли. Страничните фасади са решени аналогично на централната, но с по-пестеливи средства.

Архитектурата е разработена в стила на италианския ренесанс с явни неоренесансови влияния. Хармоничните пропорции на обемната композиция и озелененият двор допринасят сградата да се приема като палацо (дворец).

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

И до днес сградата на Варненската девическа гимназия е една от най-красивите в града, буди възхищение и е гордост за варненци.

От 3.III.1983 г. сградата е преустроена и превърната в Археологически музей. Класифицирана е като паметник от национално значение.