Juutalaisten joukkotuholle omistetun päämuistomerkin tarpeellisuudesta käytiin Saksassa 1980-luvulta alkaen vilkasta julkista keskustelua.[1] Erityinen kansalaisliike ehdotti muistomerkin sijoittamista sen nykyiselle paikalle pian Berliinin muurin murtumisen jälkeen vuonna 1990 ja vuonna 1992 Saksan hallitus ilmoitti tukevansa ajatusta. Ensimmäinen suunnittelukilpailu pidettiin 1995.[2] Yli 500 ehdotuksen joukosta valittiin voittajaksi idea, jossa jalkapallokentän kokoiseen laattaan olisi kaiverrettu jokaisen holokaustin yli viiden miljoonan uhrin nimi.[3] Liittokansleri Helmut Kohl ilmoitti kuitenkin vastustavansa ehdotusta, mikä pysäytti hankkeen etenemisen parin vuoden ajaksi. Vuonna 1997 pidettiin uusi, rajoitettu kutsukilpailu, jonka suosikiksi kohosi Eisenmanin ja Richard Serran yhteinen ehdotus. Eisenman laati ehdotuksensa pohjalta vuonna 1998 uuden suunnitelman, missä yhteydessä Serra vetäytyi sivuun. Saksan liittopäivät hyväksyivät muistomerkin rakentamisen tämän uudistetun suunnitelman mukaisesti kesäkuussa 1999. Rakennustyöt julistettiin symbolisesti alkaneiksi jo vuoden 2000 alussa, mutta tosiasiassa rakentaminen käynnistyi vasta kolme vuotta myöhemmin. Kaikki paadet saatiin paikoilleen joulukuuhun 2004 mennessä, mutta virallisesti muistomerkki vihittiin 10. toukokuuta 2005 ja avattiin yleisölle kaksi päivää myöhemmin.[2]

Saksassa jotkut arvostelivat hanketta, koska pitivät suurten muistomerkkien pystyttämistä vanhanaikaisena tai koska muistomerkki ei huomioinut muita natsien joukkotuhonnan ja vainon kohteeksi joutuneita ihmisryhmiä kuin juutalaiset. Lisäksi jotkut moittivat muistomerkin ideaa kopioksi Berliinin juutalaismuseon pihalla olevasta Daniel Libeskindin teoksesta. Valmistumisensa jälkeen muistomerkki sai kuitenkin Saksassa laajan hyväksynnän.[1] Muistomerkin rakennusvaiheessa syntyi myös skandaali, kun paljastui, että kivipaasien pintaan töhrimisen estämiseksi levitetyn kemikaalin oli toimittanut sama yhtiö, joka oli sodan aikana valmistanut IG Farbenin alihankkijana juutalaisten joukkomurhaamisessa käytettyä Zyklon B -myrkkykaasua.[3]

Muistomerkin ja sen yhteydessä toimivan näyttelyn ylläpidosta vastaa Saksan liittopäivien päätöksellä perustettu säätiö. Vuonna 2009 säätiön perustamiskirjaan tehtiin lisäys, jonka mukaan se vastaa myös Kansallissosialistien vainoamien homoseksuaalien muistomerkin sekä Kansallissosialistien murhaamien sintien ja romanien muistomerkin ylläpidosta.[4]