Në fundvitet ’40, pas përfundimit të Luftës së Dytë Botërore, iu kushtua një vëmendje e posaçme nderimit të të rënëve dhe ngritjes së një memoriali për ta. Vendndodhja e parë e Varrezave të Dëshmorëve ishin kodrat pas Korpusit Qëndror të Universitetit, pranë kishës orthodhokse të Shën Prokopit (sot janë varrezat e ushtarëve anglezë të rënë në Shqipëri gjatë luftës së dytë botërore). Ky vend, në ditët e sotme, shënjohet me një pllakatë treguese.

Në vitet që pasuan, në dobi të propagandës që glorifikonte atë pjesë historie me qëllim lënien në hije dhe errësimin e ngjarjeve dhe figurave të rëndësishme kombëtare, u pa si domosdoshmëri ngritja e një kompleksi monumental që të zotëronte fushëpamjen e Tiranës. Kështu, në vitin 1971, u zgjodh për zhvendosjen e tyre një pozicion më i dukshëm, kodra ndërmjet Pallatit të Brigadave dhe Senatoriumit, ndarë prej rrugës së Elbasanit, përkundrejt qytetit të Tiranës.

Për projektin dhe zbatimin e Varrezave të Dëshmorëve punuan arkitektë dhe inxhinierë të zgjedhur. Projektmaketi u vendos në hollin kryesor të Pallatit të Kulturës në Tiranë, ku populli mund të shikonte dhe të linte me shkrim vërejtjet dhe preferencat për variantet. Fillimisht aty u zhvendosën eshtrat e Qemal Stafës, Nako Spirut, Alqi Kondit dhe Gogo Nushit. Varret e tyre ndodheshin pikërisht te lulishtja para Galerisë Kombëtare të Arteve, në buzë të trotuarit të Bulevardit “Dëshmorët e Kombit”, por më pas u mor vendimi që të vendoseshin edhe varret e dëshmorëve të luftës antifashiste nacionalçlirimtare. Projekt maketi fitues u shpall ai i grupit të arkitektëve drejtuar nga Prof. Besim Daja.

Në qendër të kompleksit të “Varrezave të Dëshmorëve të Kombit” u vendos monumenti “Nëna Shqipëri”, 12 metër i lartë. Statuja është në beton dhe është përuruar në “Varrezat Dëshmorët e Kombit” në vitin 1971, vendosur mbi një piedestal tre metra të lartë, e veshur me pllaka mermeri, ku është shkruar “Lavdi e Përjetshme Dëshmorëve të Atdheut”. Ky monument ka për autorë skulptorët Kristaq Rama, Mumtas Dhrami dhe Shaban Hadëri.

Në kompleksin monumental të “Varrezave e Dëshmorëve të Kombit” ndodhen gjithsej 855 varre të vendosur në:

• Blloqe me nga 96 varre ose 768 varre, ndodhen në pjesën lindore të kompleksit, në bllokun e 5-të janë 104 varre për dëshmorët e rënë jashtë territorit të Shqipërisë, në Kosovë dhe në ish Jugosllavi.
• Një bllok me 62 varre ku 26 varre janë oficerë aviatorë të rënë në detyrë në vitet 1962-1993, 22 varre të policëve të vrarë në krye të detyrës mbas viteve 1990, një varr i dëshmorit Skerdilajd Llagami të rënë në luftën e Kosovës në vitin 1999, një varr të dëshmorit Feti Vogli të rënë në Afganistan. Ky bllok ndodhet në pjesën e fundit në lindje të kompleksit.
• Pranë Monumentit “Nëna Shqipëri” ndodhet në të djathtë varri Heroit të Popullit Qemal Stafës, varri Heroit të Demokracisë Azem Hajdarit, në të majtë ndodhet varri i Heroit të Popullit Vasil Shanto dhe varri i 22 viktimave të terrorit komunist të vrarë me pushkatim për ngjarjen e Ambasadës së ish -Bashkimit Sovjetik.

Dita e Nderimit të Dëshmorëve të Kombit është caktuar 5 Maji, datë në të cilën ka rënë komunisti Qemal Stafa. Varrezat e Dëshmorëve janë të përfshira në Protokollin e Shtetit si vend ku kryhen nderime dhe organizohen ceremonitë zyrtare.