Die zunächst bereits für das Jahr 2004 vorgesehenen und durch die Meinungsverschiedenheiten verzögerten Bauarbeiten zum Denkmal begannen symbolisch am 19. Dezember 2008, dem offiziellen Gedenktag des Bundesrates für die Opfer des Völkermordes an den Roma.