St. Nikolai, zwischen 1166 und 1174 begonnen, gehört zu den ältesten Backsteinkirchen der Mark Brandenburg und ist die einzige unverändert erhaltene romanische Kirche der Stadt. Sie war Pfarrkirche des Ortes Luckenberg. Das Patrozium deutet auf eine frühe deutsche Händlersiedlung hin. Die Baugeschichte der Kirche spiegelt das Schicksal der Siedlung wider, die sich vermutlich wegen der wenigen hundert Meter entfernten, ab etwa 1180 angelegten Altstadt nicht entwickeln konnte und schließlich 1298 in die Altstadt inkorporiert wurde.
Die verfallene Kirche wurde 1467 in Stand gesetzt, als sie für das Gertraudenspital genutzt wurde. Nachdem das Spital in die Altstadt verlegt worden war, diente St. Nikolai als Kapelle des umgebenden Friedhofs (heute Puschkinplatz) und in die Seitenschiffe wurden Erbbegräbnisse eingebaut. Bei der umfassenden Restaurierung 1904-10 wurden Grufteinbauten entfernt. Ein Bombentreffer zerstörte 1945 den Westbau, der verändert wiederaufgebaut wurde.
Seit der Sanierung 1990-1993 wird der Kirchenraum wie schon 1845-49 von der katholischen Gemeinde genutzt. Von der alten Ausstattung der Kirche ist nur das Triumphkreuz vom Anfang des 16. Jhs. erhalten.