Um 1083 gründete Bischof Burchard der II. das Paulsstift, konnte es zu seinen Lebzeiten jedoch nicht mehr vollenden. Erst unter Bischof Reinhard kam es Anfang des 12. Jahrhunderts zur Kirchweihe. Das Stift bestand bis zu seiner Aufhebung 1812. Die erste Kirche soll bereits vor Gründung des Klosters durch Bischof Hildegrim an dieser Stelle erbaut worden sein. Baubeginn der zweiten Kirche war zur Zeit der Klostergründung. Der romanische Bau wurde einige Male durch Feuer stark in Mitleidenschaft gezogen. Es kam zu stetigen Neubauten. Im 14. Jahrhundert begann man mit dem Bau des neuen Chores im gotischen Stil. Es war die einzige Kirche in Halberstadt die, seit dem 17. Jahrhundert, gleichermaßen von Katholiken und Protestanten genutzt wurde. Nach Aufhebung des Stiftes diente sie als Lazarett und militärisches Proviantamt. Zwischen den beiden Weltkriegen war sie Garnisonskirche. Am 8.4.1945 stark beschädigt, erfolgte 1969 der Abriss.
