Genocido aukų muziejus įsteigtas Lietuvos Respublikos kultūros ir švietimo ministro bei Politinių kalinių ir tremtinių sąjungos prezidento 1992 m. spalio 14 d. įsakymu. Jis įrengtas tame pačiame pastate, kuriame nuo 1940 m. antrosios pusės iki pat 1991 m. rugpjūčio sovietinės represinės institucijos – NKVD ir NKGB–MGB–KGB – kūrė Lietuvos gyventojų trėmimų, suėmimų, kitaminčių persekiojimo, tautos siekio atkurti nepriklausomybę gniuždymo planus. Šis pastatas lietuvių tautai yra 50-metės sovietinės okupacijos Lietuvoje simbolis, tad labai svarbu, kad kaip tik čia įkurtas muziejus, turintis dabartinei kartai priminti, o ateinančioms – papasakoti apie sunkius ir tragiškus tautai 1940–1990 metus. Muziejus unikalus tuo, kad yra vienintelis buvusiose sovietinėse respublikose, įkurtas ten, kur buvo KGB būstinė.
1997 m. muziejus reorganizuotas. Lietuvos Respublikos Vyriausybės 1997 m. kovo 24 d. nutarimu "Dėl Represijų Lietuvoje tyrimo centro ir Genocido aukų muziejaus perdavimo Lietuvos gyventojų genocido ir rezistencijos tyrimo centrui" muziejaus steigėjo teises perėmė Lietuvos gyventojų genocido ir rezistencijos tyrimo centras. Dabar muziejus yra šio Centro Memorialinio departamento dalis. Jo uždavinys – rinkti, saugoti, tyrinėti ir propaguoti istorinę – dokumentinę medžiagą, atspindinčią sovietinio okupacinio režimo vykdyto Lietuvos gyventojų fizinio ir dvasinio genocido formas, metodus, pasipriešinimo okupaciniam režimui būdus ir mastą, įamžinti sovietinio genocido aukų ir laisvės kovotojų atminimą.