1 czerwca 1967 r. cztery organizacje: Rada Ochrony Pomników Walki i Męczeństwa, Towarzystwo Opieki nad Majdankiem, Związek Polskich Artystów Plastyków i Stowarzyszenie Architektów Polskich ogłosiły „konkurs powszechny na pomnik ku czci ofiar Majdanka”. Do realizacji wybrano projekt Wiktora Tołkina i Janusza Dembka, zdobywców trzeciej nagrody. Budowa pomnika trwała dwa lata, a uroczystość odsłonięcia odbyła się podczas Dni Majdanka 21 września 1969 r.
Założenie pomnikowe składa się z trzech głównych części: PomnikaBramy, Drogi Hołdu i Pamięci oraz usytuowanego na jej osi Mauzoleum. Tołkin umiejętnie pogodził ze sobą różne tendencje estetyczne: z jednej strony wybrał tradycyjne formy architektoniczne, jak brama czy mauzoleum, z drugiej zaś nadał im silnie oddziałujące wizualnie ogromne abstrakcyjne i nieregularne kamienne formy. Artysta dokonał tu niezwykle udanej fuzji tych dwóch elementów, skutkiem pomnik zyskał ponadczasowy wygląd.
Tołkin zaburzył konstrukcję bramy poprzez drastyczną zmianę naturalnie narzucających się proporcji, stosowanych zwykle w tego typu obiektach architektonicznych. Nadproże stanowi najbardziej masywną część Bramy, rozmiarem znacznie przewyższającą jej podpory, co wzmaga wrażenie ogromnego, przygniatającego ciężaru górnej części pomnika. To właśnie to gigantyczne nadproże jest najmocniejszym estetycznie elementem całego założenia pomnikowego. Wykonana z rozmachem ogromna surowa forma o nieregularnym kształcie zbliżonym do prostokąta składa się z wielu potężnych brył, które stykając się ze sobą, tworzą wgłębienia lub ażurowe przestrzenie. Nierówna, chropowata faktura pochłania światło, a w zagłębienia pomiędzy bryłami powstają dodatkowe ciemne obszary, dając niezwykle ekspresyjny efekt i sugestywny obraz grozy. Monumentalność bramy została spotęgowana poprzez usytuowanie jej na wzniesieniu, do którego prowadzą kaskadowe schody. Kamienny fryz na zachodnim boku nasypu nawiązuje estetycznie do wzoru spiętrzonych głazów z nadproża. Przed Bramą znajduje się sześć zniczy, na których wykuto daty okupacji niemieckiej na Lubelszczyźnie: 1939–1944. Samo wejście otacza niskie metalowe ogrodzenie o ekspresyjnie poszarpanych brzegach.
Kolejnym elementem pomnika jest droga, rozpoczynająca się przed Bramą zagłębieniem w formie wąwozu, który z dwóch stron flankują potężne głazy z piaskowca. One również mają za zadanie przytłaczać potencjalnego odbiorcę. Droga, czy raczej szeroka aleja wytyczona wzdłuż pól więźniarskich i wież strażniczych, wiedzie do Mauzoleum. Ten majestatyczny obiekt nakrywa wypłaszczona kopuła, wsparta na czterech filarach i otoczona fryzem, który w warstwie wizualnej koresponduje z nadprożem Bramy. Poprzez usytuowanie Mauzoleum na wzniesieniu i jednocześnie na końcu osi widokowej zagospodarowanie przestrzeni zyskało dominujący punkt. Stanowi ono czytelny kod nawiązujący do historycznej formy architektonicznej, a zarazem stało się symbolicznym grobowcem dla wszystkich ofiar obozu na Majdanku.
Na różnych elementach pomnika Tołkin umieścił inskrypcje, które dopowiadają i formułują to, czego może nie ujawniać zaproponowana przez niego forma. Na fryzie kopuły widnieje napis: „Los nasz dla was przestrogą”, pochodzący z wiersza Franciszka Fenikowskiego Requiem. Na prawym pylonie umiejscowiony został podpis Tołkina, który sam był więźniem Auschwitz, utożsamiał się więc niezwykle mocno ze swoimi rzeźbami wykonywanymi w byłych obozach. Przy lewym pylonie Bramy znajduje się tablica z tekstem:
„Bohaterom Majdanka, którzy walcząc przeciw hitlerowskiemu ludobójstwu o wolność swych narodów i całej ludzkości, broniąc ideałów człowieczeństwa i godności własnej ponieśli tu śmierć męczeńską. Rada Państwa Polskiej Rzeczypospolitej Ludowej jako wyraz pamięci i hołdu dla ich męczeństwa i walki z faszyzmem nadaje Order Krzyża Grunwaldu 1 klasy. Warszawa 1969 20 września”.
