На 7 декември 1994 година Столичният общински съвет взема решение за изграждане на мемориал, който да ни напомня за жертвите на комунизма в България от периода на създаването на Българската комунистическа партия през 1919 година до свалянето на Тодор Живков от власт през 1989 година. Мемориалният комплекс е посветен на всички жертви на БКП: на пострадалите от терористичните актове на левите екстремисти, на убитите без съд и присъда достойни българи, на хилядите наши сънародници, изпратени в лагери, на преселваните, преследваните и репресираните.
За да бъде избрана визията на мемориала, се провежда национален конкурс, организиран от Фонд „Паметник на жертвите на комунизма”. Печели проектът на арх. Атанас Тодоров, арх. Димитър Кръстев и инж. Цветан Иванов. Мемориалният комплекс е изграден в периода 1997 – 1999 година от фонд „Паметник на жертвите на комунизма”, като строителните работи са дело на фирма „Бокар” и фирмата за каменни облицовки „Европа 97”. Надписите върху Паметната стена са дело на художниците Иван Смолянов и Кирил Николчев, а мозайките в параклиса „На всички български мъченици” – на художника Асен Гицов. Красноречив е фактът, че средствата за изграждането на мемориала са дарени от стотици родолюбиви българи и са събрани за изключително кратко време. Паметникът е открит официално на 11 септември 1999 година с тържествена църковна служба, отслужена от свещеници и архиереи на Българската православна църква и духовници от Католическата и Арменската църкви, като този акт за пореден път демонстрира единството на всички жертви и пострадали от комунизма.
Мемориалният комплекс се намира в източната част на парка пред Националния дворец на културата (НДК) и се състои от три отделни елемента, които сами по себе си са изключително впечатляващи, но взети заедно формират едно място на памет с невероятна сила и въздействие. Първият елемент е облицованата с черен гранит Паметна стена с дължина 58 метра, върху която са изписани имената на 7526 жертви на комунизма в България. Пред централната част на Паметната стена е вкопан старинен християнски оброчен кръст, който служи за символичен надгробен знак. В близост е разположен и малък православен параклис, изграден от бял камък, който е посветен на всички български мъченици, за да ни напомня за страданията на жертвите, но и за голямата им любов към България и към българския народ. Самият мемориал е разположен до малък хълм, който сякаш е част от цялостната композиция и може да бъде възприет като символична гробна могила на всички жертви на комунизма, тъй като много от убитите са погребани в безименни гробове и днес близките им дори не знаят къде почиват тленните им останки. По този начин съхраняваме паметта за загиналите и им отдаваме почитта, която заслужават. Мемориалният комплекс, посветен на жертвите на комунизма е едно силно въздействащо кътче в центъра на столицата ни, което носи много поуки и към което си струва да се връщаме всяка година.
