Im Oktober 2005 beschloss die Stadtverordnetenversammlung Cottbus mit großer Mehrheit das Projekt Stolpersteine. Im Mai des folgenden Jahres stellte der Künstler Gunter Demnig in der Schlosskirche (seit 9. November 2015 Synagoge) sein Kunstprojekt einer breiten Öffentlichkeit vor. Das Projekt wurde anregt diskutiert und stieß bei vielen Bürgerinnen und Bürgern auf großes Interesse.

Die ersten elf Stolpersteine konnten am 29. September 2006 vor fünf Wohnhäusern verlegt werden, am 24. Oktober wurden aber bereits die Steine für Bertha Pakulla und Bernhard Freykor von Unbekannten gestohlen. In der folgenden Stadtverordnetenversammlung sammelten die empörten Stadtverordneten, Verwaltungsmitarbeiter und Gäste einen Betrag, der den Ersatz der zwei Steine und die Finanzierung zwei weiterer Stolpersteine ermöglichte. Die entwendeten Steine konnten am  29. November ersetzt werden.

Am 14. November wurden in der Bahnhofstraße fünf weitere Stolpersteine für die Familie Hammerschmidt gestohlen. Die in der Nähe befindlichen Stolpersteine für Adele und Georg Schlesinger wurden mit Teer beschmiert. Die Schändung der Gedenksteine sorgte für eine landesweite Welle der Empörung. Auf dem Tag der Demokraten in Halbe sammelten die Demonstranten für den Ersatz der Steine. Aus dem Erlös konnte neben den entwendeten Steinen ein weiterer Stolperstein finanziert werden. Bereits am 13. Dezember wurden die in der Bahnhofstraße entwendeten Steine ersetzt. Die Anschläge auf die Mahnmale führten bei den Bürgerinnen und Bürgern der Stadt Cottbus zu einer starken Solidarisierung mit dem Projekt der Stolpersteine.

Im Juni 2007 wurden die Stolpersteine für Adele und Georg Schlesinger erneut beschmiert sowie die Metalloberfläche beschädigt. Eine nach den vorherigen Vorfällen begründete Kooperation zwischen Stadtverwaltung und Polizei sorgte für eine schnelle Beseitigung der Schäden. Auch 2008, 2012 und 2014 kam es zu Beschmutzungen oder Beschädigungen von Stolpersteinen, die aber aufgrund aufmerksamer Bürgerinnen und Bürger schnell gemeldet und beseitigt werden konnten.

Insgesamt wurden seit 2006 in der Stadt Cottbus 90 Stolpersteine vor 37 Cottbuser Wohnhäusern durch Gunter Demnig in das Straßenpflaster verlegt. Möglich war dies über die Jahre durch die Spenden aus der Cottbuser Bevölkerung und durch die Übernahme von Patenschaften.

Im Juni 2010 übernahm der Historische Heimatverein Cottbus e.V. die Trägerschaft über die Cottbuser Stolpersteine.

Im November 2012 erhielt Frau Breitschuh-Wiehe als Initiatorin des Cottbuser Stolpersteinprojektes die Ehrenmedaille der Stadt Cottbus.