Подземный комплекс общей площадью около 15 тыс. м2 был спроектирован ленинградским проектным институтом «Гранит». В 1947 году проект завизировал Сталин, однако строительство основной части комплекса началось уже после смерти генсека — в 1953 году. Для проведения работ был сформирован специальный горно-строительный отряд Черноморского флота. Отряду было поручено вести первый этап строительства подземного убежища. Следом за военными в Балаклаву приехали строители; участие гражданских специалистов было обусловлено сложностью бурения горных пород. Гора Таврос, в недрах которой расположился секретный объект, состояла из прочного мраморовидного известняка.
В 1956 году было создано Строительное управление 528. Везде были только цифры, и никаких названий. Номер строительного управления был выбран из трех цифр, входящих в номер «Объекта 825 ГТС», только их переставили местами. По личному распоряжению Никиты Хрущева в стройуправление вошли специалисты Метростроя из Москвы, Харькова и имеющие опыт горнопроходческих работ на Кавказе строители из Абакана.
Материально-техническая база СУ 528 располагалась в Балаклаве в 3 км от основных работ. Территория базы была обнесена изгородью из колючей проволоки. Там находились центральный материальный склад, бетонный цех со складом цемента и песка, мастерская монтажно-механического участка, автогараж и склад горючего, лесопильный и столярный цех со складом лесоматериалов.
В распоряжении стройуправления имелся центральный склад взрывчатых веществ, расположенный на горе за базой, и раздаточный склад ВВ, в районе основных работ.
Строительство велось круглосуточно, в три смены, буровзрывным методом. Бурились шурфы, в них закладывался взрывчатый заряд, разрушающий породу на нужной глубине. Грунт вывозили, внутри образовавшейся штольни строили опалубку для бетона. Существенный недостаток буровзрывного метода заключался в слабопредсказуемой форме штольни и, как следствие, необходимости возводить опалубку переменной толщины. Поэтому толщина обделки стен и сводов сооружения в среднем составляла 1,5 м, а на отдельных участках достигала 3 м. После вывоза грунта рабочие устанавливали металлический каркас. Затем его дополняли деревянными элементами и, наконец, забивали бетоном марки «М 400». Вплоть до 1956 года бетон подавался вручную, лопатами. Потом его стали закачивать в форму сжатым воздухом.
Так продолжалось почти восемь лет. При строительстве было вывезено около 120 тыс. т породы, этого бы хватило, чтобы построить пирамиду Хеопса. Для обеспечения секретности породу вывозили ночью на баржах в открытое море и затем сбрасывали в воду.
Строительство «Объекта 825 ГТС» было завершено в 1961 году. Комплексу присвоили первую категорию противоатомной устойчивости. Это означало, что 128 м породы и бетона над внутренними помещениями объекта должны обеспечить защиту от прямого попадания атомной бомбы мощностью в 100 кт (для сравнения, Хиросиму уничтожила бомба мощностью в 20 кт). В комплексе могли укрыться от ядерной атаки семь подводных лодок среднего класса или же четырнадцать субмарин малого и среднего классов. Кроме того, объект мог вместить до трех тысяч человек, а это — весь личный состав и большая часть жителей Балаклавы. Годом позже в эксплуатацию была передана минноторпедная часть, еще год спустя — «Объект 820», он же «Арсенал»: подземная ремонтно-техническая база для хранения, сборки и установки на подводные лодки боеприпасов с ядерными боевыми зарядами.
Стоимость «Объекта 825 ГТС» составила 67 млн советских рублей (по старому курсу, до 1961 года). Еще 65 млн было потрачено на внутренние системы секретного объекта.
В основе комплекса — искусственный тоннель длиной более 600 м, глубиной и шириной до 8,5 м и высотой 18 м. Толщина скалы над тоннелем в наивысшей точке достигает 126 м. Вход и выход (один — в бухту, другой — в открытое море) были тщательно замаскированы. Со стороны бухты вход в штольню перекрывался стопятидесятитонным плавучим батопортом, который всплывал после поддувания воздухом. Это позволяло полностью «закупоривать» подземный объект. В секретных цехах насчитывалось от 170 до 230 человек, обслуживавших док и другие инженерные системы комплекса. Полсотни постовых круглосуточно охраняли базу. В охранной системе вместе с колючей проволокой использовали сигнальные мины и электрический ток. Общая площадь всех подземных сооружений превышала 15 тыс. м2, а канал, по которому проходили подлодки, был шире самой Балаклавской бухты. Отдельные помещения достигали высоты трехэтажного дома.