Në fundvitet ’40, pas përfundimit të Luftës së Dytë Botërore, iu kushtua një vemendje e posaçme nderimit të të rënëve dhe ngritjes së një memoriali për ta. Vendodhja 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 Tiarnë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 Elbasanit, përkundrejt qytetit të Tiranës.

Idenë për ndërtimin e kompleksit monumental të “Varrezave të Dëshmorëve të Luftës së Dytë Botërore” e hodhi Enver Hoxha. Për projektin dhe zbatimin punuan arkitektë dhe inxhinierë të zgjedhur nga qeveria komuniste dhe 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. Projektmaketet e përzgjedhura më pas do të kalonin edhe në filtrin e udhëheqjes më e lartë e Partisë së Punës, Byrosë Politike. 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”. Nuk ishte parashikuar të bëheshin varrime të tjera, me përjashtim të udhëheqjes së asaj kohe mbas vdekjes, por më pas u mor vendimi që të vendoseshin edhe varrezat 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, Muntaz Dhrami dhe Shaban Hadëri.

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

• Tetë 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 46 varre ku 24 varre janë oficerë aviatorë të rënë në detyrë në vitet 1962-1993, 20 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 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.

839 varre janë të Dëshmorëve të Kombit, 30 varre janë të Heronjëve të Popullit. 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.