Die Stephanskirche befindet sich auf der höchsten Erhebung Tangermündes - dem Prälatenberg. Sie zählt zu den herausragenden Bauwerken der norddeutschen Backsteingotik.Verschiedene Quellen schrieben dem Turm eine Höhe von 94 Metern zu. Einige wenige Tangermünder und auch Touristen äußerten über viele Jahre Zweifel an dieser enormen Höhe. Erst die Vermessung des Turms im Zuge der Sanierung (1998-2000) sollte den Skeptikern Recht geben und ergab eine Höhe von "nur" 87,5 Metern. Aber auch mit dieser Höhe darf St. Stephan für sich weiterhin beanspruchen, der höchste Kirchturm in der Altmark zu sein.
Das erste nachweisbare Bauwerk ist eine romanische Backsteinkirche von vor 1188. Von diesem sind Teile im heutigen Bau erhalten- an der Außenwand des letzten Langhausjoches befindet sich zwischen zwei kleinen gotischen Rundbogenfenstern ein romanisches Fenster. Die ursprüngliche Planung in den 80-er Jahren des 12. Jahrhunderts, an St. Stephan in Tangermünde ein Domherrenstift einzurichten, wurde letztendlich zu Gunsten der in Stendal befindlichen Kirche St. Nikolaus entschieden.