Zum fünfzigsten Jahrestag setzte sich Demnig 1990 künstlerisch mit den Deportationen von 1000 Roma und Sinti aus Köln auseinander, die für die Nationalsozialisten eine Art Generalprobe für die nachfolgenden umfangreicheren Judendeportationen waren. Mit einer Art rollbaren Druckmaschine zog er den Deportationswegen folgende Spuren durch die Stadt. Einen ersten mit einer Messingplatte versehenen und beschrifteten Stein ließ Demnig am 16. Dezember 1992, dem 50. Jahrestag des Befehls Heinrich Himmlers zur Deportation der ‚Zigeuner‘, vor dem Historischen Kölner Rathaus in das Pflaster ein. Auf dem Stein zu lesen sind die ersten Zeilen dieses Erlasses. Demnig mischte sich mit diesem Stein in die Diskussion um das Bleiberecht von aus Jugoslawien geflohenen Roma ein.
Die gewichtigste Kritik an Demnigs Projekt kommt von Charlotte Knobloch, der ehemaligen Präsidentin des Zentralrats der Juden in Deutschland, die es als „unerträglich“ bezeichnet hat, die Namen ermordeter Juden auf Tafeln zu lesen, die in den Boden eingelassen sind und auf denen mit Füßen „herumgetreten“ werde.[6] Die Meinungen gehen im Zentralrat der Juden jedoch auseinander, und der Vizepräsident Salomon Korn verteidigt das Projekt.[7] Städte, die die Verlegung von Stolpersteinen ablehnen, berufen sich meist auf die Kritik von Knobloch. Das bekannteste Beispiel ist München, wo die beiden einzigen auf öffentlichem Grund verlegte Stolpersteine wieder aus dem Bürgersteig der Mauerkircherstraße entfernt wurden, da Stadtrat und jüdische Gemeinde gegen Stolpersteine sind.[8] Die beiden entfernten Stolpersteine kamen nach einer Zwischenstation auf dem jüdischen Friedhof in die Münchner Musikhochschule und sind nun Teil einer künstlerischen Installation. In München gibt es nur Stolpersteine auf Privatgrund. 120 Stolpersteine für Münchener Opfer wurden bereits hergestellt und können nicht verlegt werden.
In Hamburg haben wir in allen etwas "betriebsameren" Straßen solch Stolpersteine. Einerseits finde ich diese Idee gut denn wir sollen unserer Ahnen gedenken so oft wir können. Andererseits bin ich, was dieses ewige Erinnern an die Ermordung so vieler Juden betrifft, im Zwiespalt. Ich persönlich habe überhaupt keine Berührungspunkte mit diesem Glauben. Die deutsche Geschichte ist für mich ein eher widerlich und unangenem. Ich kann die Menschen die sowas tun einfach nicht nachvollziehen. Andererseits bin ich nun mal unleugbar Deutsche. Aber auf einem ganz anderen Level, wie ich finde. Die Israelische Politik in Richtung Deutschland tut ihr übriges. Mein Gefühl ist, dass wir ständig und zuviel daran erinnert werden wer wir mal waren. Was haltet ihr davon?
Ich war nie dabei, habe nie jemanden ermordet und schon lange keine Roma und Juden. Wir Deutsche leben seit 1945 in Frieden, während die Juden seit 1956 Krieg führen. Da möchte ich doch gerne mal wissen, warum ich mich an das erinnern soll, was mein Vater und Opa gemacht haben, während die Juden weiter morden und krieg führen dürfen. Warten wir mal ab, was die Juden im September/Oktober mit dem Iran vor haben. Das sie einen weiteren Krieg beginnen werden, haben sie angekündigt. Und wie sie den krieg führen wollen, haben sie auch angedeutet. Wenn irgendwo Stolpersteine aufgestellt/installiert werden müssen, dann in Israel, genau da, wo Palästinenser Libanesen und Ägypter von Juden umgebracht wurden. Alle Deutschen, die nach 1940 geboren wurden, brauchen sich nicht um die Stolpersteine zu kümmern. Sie haben eh keinen Bezug dazu. Man kann sich die Vergangenheit im Fernsehen ansehen, aber eben auch die Gegenwart. Und die zeigt uns ein äußerst gewalttätiges Israel, das mit Atombomben auf den Iran schießen will. Das muß ich als friedliebender Deutscher nicht verstehen, oder?