При Н.С. Хрущеве мемориалы стали «памятью военно-исторических событий», Могила Неизвестного Солдата — «апофеозом всенародной скорби о павших», а Вечный огонь — «символом бессмертия». Средств на «внешнее оформление» теперь не жалели. В 1957 г. в Ленинграде на Марсовом поле впервые в СССР был зажжен Вечный огонь, первым военным мемориалом стало Пискаревское кладбище.
В том же году Госстрой БССР объявил всесоюзный конкурс на разработку проекта. Участие в нем приняли сотни художников, скульпторов, архитекторов. Большинство авторов располагали монумент в центре Цитадели, однако были предложения разместить его на Восточном валу крепости, врезав в земляной объем, или вынести за пределы крепости. Конкурсы и проектные работы проводились с 1959 по 1960 г., однако ни один проект не удовлетворил заказчика.
23 июня 1961 г. состоялась первая большая встреча защитников крепости, приехавших в Брест из разных городов Советского Союза. Через день недалеко от музея был заложен камень будущего монумента в честь героической обороны. В 1964 г. организационный комитет по подготовке празднования 20-летия освобождения Белоруссии объявил сбор средств на строительство монумента. Средства поступали со всех уголков страны, но что строить, по-прежнему, было непонятно.
6 мая 1965 г. лейтенанту А. М. Кижеватову присвоили звание Героя Советского Союза посмертно. Еще около 200 участников обороны были награждены орденами и медалями, в том числе посмертно. Их именами стали называть улицы, школы, пионерские дружины, пограничные заставы и пароходы. В крепости прошел молодежный праздник «Брестская весна», в ходе которого возле здания красноармейского клуба был зажжен газовый факел, символизирующий Вечный огонь.
8 мая 1965 г. Брестской крепости было присвоено почетное звание «Крепость-герой», вручен орден Ленина и медаль «Золотая Звезда», которые находятся на вечном хранении в Музее обороны. Понятие «город-герой» ввел в оборот маршал И.В. Сталин. В приказе № 20 от 1 мая 1945 г. Верховный Главнокомандующий назвал городами-героями Ленинград, Сталинград, Севастополь и Одессу. Двадцать лет спустя кому-то в Политбюро пришла в голову идея присваивать геройские звезды отдельным городам, «трудящиеся которых проявили массовый героизм и мужество в защите Родины в Великой Отечественной войне». К сталинскому перечню добавили Москву, Киев и Брестскую крепость. В дальнейшем на каждый юбилей список пополняли, в него вошли Керчь и Новороссийск, Минск и Тула, Смоленск и Мурманск.
19 сентября в крепости состоялся 1-й Всесоюзный слет победителей похода молодежи по местам боевой славы советского народа. Участники слета заложили на склоне Восточного форта аллею героев. У порохового погреба на Кобринском укреплении зажгли Вечный огонь, доставленный с Марсова поля, который затем был перенесен к памятному камню в центре Цитадели. Возле огня был учрежден Пост Памяти. Крепость стала местом приведения призывников к воинской присяге.
Новый тур открытого конкурса на составление проекта памятника-монумента был проведен в 1965 и 1966 гг., и снова жюри решило, что ни один из представленных проектов «не раскрывает поставленную задачу и не может быть рекомендован к осуществлению в натуре». Наконец в 1967 г. была создана творческая группа под руководством известного советского скульптора А. П. Кибальникова, в состав которой вошли скульпторы А. Бембель и В. Бобыль, архитекторы В. Король, В. Волчек, В. Занкович, О. Стахович, Г. Сысоев. В Минске организовали специализированную мастерскую при Союзе архитекторов Белоруссии. В 1967–1969 гг. авторский коллектив на основе своих конкурсных материалов разработал окончательное решение всего мемориального комплекса и совместно с инженерами-конструкторами, инженерами по дорожному строительству и благоустройству, светотехниками выполнил модели и рабочие чертежи всех сооружений.
6 ноября 1969 г. Совет Министров БССР утвердил генеральный план создания на территории Брестской крепости мемориального комплекса, первую очередь которого намечалось открыть к 30-летию начала Великой Отечественной войны. Основным подрядчиком по сооружению объектов стал трест № 8 Министерства промышленного строительства Белоруссии. Работы на территории крепости возглавил начальник управления треста С.В. Бриль. В возведении мемориала принимали участие 25 строительно-монтажных организаций Советского Союза.
Вечный огонь на время перенесли в западную часть Цитадели к руинам казарм 333-го стрелкового полка.