Bei diesem Projekt handelt es sich um das Vorläufer-Projekt zu den STOLPERSTEINEN. Es hieß: MAI 1940 – 1000 ROMA UND SINTI. Es gibt einen Bericht, der das Zustandekommen dieser Aktion authentisch schildert: „Gunter lernte ich Anfang 1990 im Friesenviertel in der Kneipe Grüneck kennen‘, erzählt Kurt Holl, Gründungsmitglied des Rom e.V. ‚Er arbeitete damals an einem Projekt, das zum Ziel hatte, den ersten Artikel der Menschenrechtserklärung der UNO in alle Sprachen der Welt in Bleiplatten [Tontafeln. Gemeint ist das Projekt „Gesetzestafeln“, d. A.] zu gravieren und zwar in der internationalen Lautschrift. Er bat mich, ihm die Übersetzung auf Romanes zu besorgen. Wir unterhielten uns über seine bisherigen Kunstaktionen, etwa über das Projekt Ariadne-Faden […]. Ich fragte ihn, ob er sich vorstellen könne, zum 50. Jahrestag der Deportation der Roma und Sinti, der bevorstand, eine ähnliche Spuraktion zu konzipieren. Zwei Wochen später ließ sich Gunter aus dem Vereinsarchiv und von der Historikerin Karola Fings alle historischen Daten über dieses Ereignis geben. Dann präsentierte er folgenden Vorschlag: Vom Ausgangspunkt der Deportationsmaßnahme, dem Schwarz-Weiß-Platz im Kölner Westen bis zum Lager in der Kölner Messe, jenseits des Rheins, werde eine Farbspur gelegt, die zugleich durch die damaligen Wohnviertel der Roma und Sinti führt, also dem Weg, den die LKWs nahmen, als sie die Familien abholten.‘ […] Der 1,2m lange Text der Spur, der nahtlos mehrere tausend Mal mit Hilfe einer Schablone abgerollt wurde, sollte lauten: Mai 1940 – 1000 Roma und Sinti.“

Am 6. Mai 1990, Sonntagmorgens um sechs Uhr (zu diesem Zeitpunkt begannen auch die Deportationen der Sinti und Roma), begann bei strahlendem Sonnenschein die Aktion. Keiner der Beteiligten konnte 1990 ahnen, dass diese Kunstaktion zur Geburtsstunde der STOLPERSTEINE führen würde. Zumal zunächst auch die Gefahr drohte, dass Demnigs Spur, auch wenn sie mit schwerlöslicher Außenbinderfarbe aufs Pflaster aufgetragen worden war, verschwand, wie die Spuren anderer Projekte, und somit vermutlich ‚nur‘ eine Dokumentation dieser Kunstaktion die Zeiten überdauert hätte. Große Teile der Spur überstanden den Sommer  und am 5. Oktober 1990 stellte der Rom e.V. den Antrag, die Spur unter Denkmalschutz zu stellen und dauerhaft zu erhalten. Es begann ein langer Weg durch die Bürokratie. Zunächst machte sich der Kulturdezernent der Stadt, Peter Nestler, die Idee zu eigen und regt an, einen Teil der Spur zu konservieren. 1991 kaufte das Kölnische Stadtmuseum einen Spurabdruck auf schwarzer Pappe und hing ihn in die Dauerausstellung. Dann kam das Projekt ins Stocken. In dieser Situation entschloss sich Demnig zu einer weiteren, spektakulären Aktion: Am 16. Dezember 1992 gräbt der Künstler – wieder zusammen mit Rom e.V. – vor dem Historischen Rathaus in Köln einen Stein in das Pflaster, mit einem in eine Deckplatte aus Hartmessing geschlagenen Text. Es ist der so genannte Auschwitz-Erlass Himmlers vom 16. Dezember 1942, der die Deportationen der Sinti und Roma im März 1943 anordnet. Demnig nennt diesen Stein: STOLPERSTEIN.

Im März 1993, 50 Jahre nach den Auschwitz-Deportationen der Sinti und Roma, beschloss der Rat der Stadt Köln, „der dauerhaften Sichtbarmachung des Leidensweges der Roma und Sinti im Mai 1940 in Form von eingelassenen, beschrifteten Platten in die Gehwege“ zuzustimmen – mit dem Zusatz: „Der Rat nimmt die Maßnahme als Schenkung entgegen.“ Bezahlen wollte er dafür nicht. Die Kosten für die an 23 Stellen in der Stadt einzulassenden Schriftzüge übernehmen private Sponsoren. Der Ratsentscheidung wurde jedoch vorgegriffen als bereits Ende Januar 1993 der erste Messingschriftzug vor dem Kölnischen Stadtmuseum in das Straßenpflaster eingelassen wurde. Direktor Dr. Werner Schäfke hatte den Künstler gebeten, anlässlich der Initiative „Kölner Museen gegen Fremdenhass“ einen Schriftzug vor dem Museumsgebäude zu setzen. Die Patenschaft übernahm der Verein der Freunde und Förderer des Stadtmuseums.

Beim Verlegen des Messingschriftzugs am Großen Griechenmarkt wurde Demnig von einer Frau angesprochen. Sie behauptete, dass hier ja gar keine Zigeuner gewohnt hätten. Diese Bemerkung führte Demnig zu einer neuen Überlegung. „Die Menschen in dem Viertel lebten ganz normal, nachbarschaftlich zusammen. Zigeuner waren wie anderen gemeinschaftlich eingebunden, mit den jüdischen Mitbürgern muss es ähnlich gewesen sein. Es interessierte nicht, ob jemand vielleicht fremd oder anders aussah, etwas anderes glaubte oder einer anderen Volksgruppe angehörte. Und trotzdem wurden diese Menschen später deportiert, ohne nennenswerten Widerstand ihrer Nachbarn. Auschwitz war der Ziel- und Endpunkt, aber in den Wohnungen und Häusern begann das Unfassbare, das Grauen.“  Die Folge dieser Überlegung: die STOLPERSTEINE.

Am 3. September 2014 setzte Demnig die Ersetzung der Spur durch dauerhafteres Material fort. Die Fotos zeigen die Verlegeaktion vor dem Historischen Rathaus in Köln.