Pertraktacje rozpoczęły się w 1992 r., kiedy rząd Niemiec obiecał przedstawicielom Sinti i Romów, że w Berlinie zostanie wzniesiony pomnik dla cygańskich ofiar nazizmu; wtedy też liczbę zamordowanych w czasie wojny oszacowano na 500 tys. W tym samym roku władze państwowe i miejskie podjęły decyzję o lokalizacji miejsca pamięci wśród drzew Tiergartenu, nieopodal Reichstagu. W czerwcu 1999 r., na specjalnej sesji Bundestagu, podjęto decyzję wzniesienia w stolicy Niemiec centralnego monumentu dla pomordowanych Żydów Europy, a także oddzielnych pomników pamięci dla „wszystkich innych ofiar zbrodni narodowego socjalizmu przeciwko ludzkości”. Decyzja ta stała się podstawą dla dalszych prac nad upamiętnianiem tragedii Sinti i Romów, jak również budowy pomnika dla pomordowanych homoseksualistów.
W 2000 r. Romani Rose, przewodniczący niemieckiej Centralnej Rady Sinti i Romów, zaprosił do zaprojektowania miejsca pamięci izraelskiego artystę Daniego Karavana. Negocjacje toczyły się dalej, w lutym 2005 r. została ostatecznie zatwierdzona lokalizacja i budżet w wysokości 2 mln euro (faktycznie koszty wyniosły 2,8 mln). Sprawą sporną stały się teraz teksty na monumencie, m.in. użycie słowa Cyganie (niem. Zigeuner), kojarzące się w niemieckim ze słowem złodziej. Problemem okazało się też uzgodnienie liczby ofiar: Niemcy mówili o 100 tys. zgładzonych, z drugiej strony padały dane szacunkowe – 0,5 mln, a nawet 1 mln (ostatecznie zdecydowano się nie podawać liczb).
W 2008 r., kiedy wreszcie rozpoczęły się prace budowlane, a datę odsłonięcia ustalono na październik 2010 r., pojawiło się nowe źródło konfliktu, w którym stroną stał się projektant Dani Karavan. Zatrzymał prace i oskarżył Wydział Budowlany miasta Berlin o nieprzestrzeganie standardów w konstrukcji i używanie tanich materiałów.