Der Kölner Künstler Gunter Demnig hat auf Anregung des Rom e.V. ab Mai 1990 das inzwischen europaweit bekannte Projekt „Stolpersteine“ zuerst in Köln realisiert und zwar zunächst zur Erinnerung an die im Mai 1940 von Köln aus deportierten Sinti und Roma.
Anlässlich der 50. Wiederkehr dieses Jahrtages der Deportation realisierte Gunter Demnig auf Initiative und mit praktischer Unterstützung des Rom e.V.am frühen Sonntagmorgen des 20.Mai 1990 zunächst eine 15 km lange Lackspur quer durch Köln. Diese Spur markierte den Weg, den die LKWs der Kölner Polizei zurücklegten, als sie am 16. Mai 1940 die Sinti und Roma vom Lager in Ossendorf zum Sammellager Deutzer Messe verbrachten, von wo aus sie nach Polen verschleppt wurden. Die Spur wiederholte den Satz „Mai 1940 – 1000 Sinti und Roma“ viele Hundert Mal. Bevor die Spur wieder zu verblassen drohte, stellt der Rom e.V. den Antrag an die Stadt Köln, die Spur unter den Denkmalschutz zu stellen. Schließlich konnte durchgesetzt werden, dass die Spur an 25 markanten Stellen als Schrift in Messing gegossen und einbetoniert wird: u.a.am Polizeipräsidium, vor dem Dom, vor dem Stadtmuseum und natürlich vor der Deutzer Messe. Diese zweite Phase wurde 1990/91 realisiert.