Süring schreibt 1568 „Schultzenstraße“. 1648 war bereits die Schreibart „Schulzenstraße“ gebräuchlich.
1880 befanden sich hier 45 Grundstücke mit den Nummern 475-484, 485/6, 491-495, 496/7, 498a,b, 500, 501, Küsterhaus, 502-507, 515-525, 526/7, 528-532.
1892 waren es noch 45 Grundstücke und die Nummern 476-484, 485/6, 491-498,a,b, 500-507, 515-525, 526/7, 528-532, 583.
1938 wurden 43 Häuser gezählt mit den Nummern 476-484, 485/6, 491-495, 496/7, 498, 500,a,b, 502-507, 515-525, 526/7, 528-532.
1321 lag an dieser Straße die „curia prefecti“, der Schulzenhof, nach dem sie benannt wurde. Die Kanalisation wurde 1916 fertiggestellt.
Auf dem Platz der bisherigen Armen- oder Nikolai-Parochialschule wurde am 3. August 1835 der Grundstein für eine neue Schule gelegt, die 1838 fertig wurde mit einem Kostenaufwand von 5.410 Talern. 1872 wurde hieraus eine Mittelschule, für die 1882/3 mit 18.828,21 Mark ein Anbau errichtet wurde.
Die auf dem Kasernenhof stehende Ruine ist der Turmrest der im Mittelalter erbauten St. Nikolaikirche . 1375 traten die Dominikanermönche diese Kirche an die Stadt ab. Sie war eine gotische, dreischiffige Basilika mit zwei Seitenschiffen. Bis 1568 wurde hier noch Gottesdienst abgehalten. Im gleichen Jahr stürzte ein Teil des Schiffes ein, während 1648 der nördliche Turm und die Spitze des südlichen und bald darauf das ganze Gewölbe des Schiffes einstürzten. Die Reste des Langhauses trug man 1737 und 1769 ab und errichtete aus den Steinen die heute nicht mehr vorhandene Kirchhofsmauer sowie die Kaserne I. Die Gegend um den Turm bezeichnete man im 17. Jahrhundert als „wüste Kirche“ und den darum liegenden Friedhof als „Wüster Kirchhof“.
Turmrest und Südturm wurden später durch Satteldächer eingedeckt und der Turm noch bis 1945 als Glockenturm für die zur Dominikanerklosterkiche Zum Heiligen Kreuz verzogene Gemeinde benutzt. 1945 brannte der Turm aus.
Der Friedhof zwischen der Kasernenstraße und alten Klosterkirche hieß „der grüne Kirchhof“, wo noch bis 1768 Bestattungen vorgenommen wurden. Das Eisengitter stammt aus dem Jahr 1896.
Auf dem Pfarrhof befindet sich noch ein uralter Kesselbrunnen, der oben 2,5 m und in Wasserspiegelhöhe 1,5m lichte Weite hat. Das Wasser steht etwa 12 m tief. Er wurde 1770 nachrichtlich für das Pfarrhaus und Kloster benutzt.
1927 deckte man ihn durch zwei Schienen und eine 30 cm dicke Betonschicht ab und überpflasterte ihn.
Auf dem Stadtbauamtsgrundstück stand das 1725 erbaute und noch 1863 genutzte Salzmagazin oder die „Salzfaktorei“. 1882 richtete die Garnison hier ihre Hauptwache ein. Das Gebäude wurde 1882 abgerissen und das Kasernengrundstück durch eine Mauer mit Torweg abgeschlossen. Später entstand dann das Stadtbauamt, nachdem es vorher als Speisehaus massiv erbaut war.
In Nr. 504 hielt sich ab 1894 das Siechenhaus „Salem“ auf und in Nr. 526 war 1857 das Kreisgericht untergebracht. Nr. 529 war ein altes Giebelhaus. Die Druckerei Ragoczy hatte in Nr. 522 ihre Arbeitsstätte und 1762 in Nr. 498/9.
Vor dem Hause des Kaufmanns Kretschmar war 1871 die Haltestelle für eine Droschke, und der Briefkasten hing 1892 am Grundstück 492/3.
Eine Branntweinbrennerei betrieb der Gastwirt Karl Mertens 1850 in Nr. 484. Am 1. Oktober 1850 eröffnete in Nr. 484 F. Bredikow unter dem Namen „Restauration zum Badischen Hause“ ein Frühstücks- und Billardlokal. Von Langmann übernahm am 24. Juli 1880 E. Radsch diese Gaststätte, die bereits am 23. Dezember 1880 Otto Zeppenfeld als Eßlokal innehatte, als dessen Nachfolger F. Neumann 1882 genannt wurde. 1884 hieß das Lokal „Zum Franziskaner“ unter dem Gastwirt A. E. Barth, und 1887 übernahm es W. Hangohr.
Eine Stehbierhalle hatte 1883 A. Weirich in Nr. 528, während im gleichen Jahr im Nachbarhaus Nr. 529 A. Bülow eine Weinhandlung betrieb.
Auch Nr. 496 beherbergte eine Gaststätte. 1872 gab F. Heitchen die Eröffnung des renovierten Lokals bekannt. 1882 veranstaltete W. Schulze hier musikalische Abendunterhaltung. 1883 war E. Heiland der Restaurateur, und im April 1891 annoncierte Christian Müller die Übernahme des Lokals, wogegen im gleichen Haus und im gleichen Jahr W. Ehrke eine Übernahme zum Gastwirt Dorn meldete.
In Nr. 526/7 hatte Ende des vorigen Jahrhunderts die Ressourcengesellschaft ihren Zusammenkunftsort und in Nr. 505 befand sich der bekannte „Gemütliche Winkel“.
1945 brannten alle Häuser nördlich der Kleinen Kasernenstraße und Hospitalstraße ab.
Am 29. Dezember 1950 wurde sie zusammen mit der Königstraße , mit der sie in gar keinem Zusammenhang steht, in „Straße des Friedens“ und ab 1964 in Heinrich-Heine-Straße (die zweite Heinrich-Heine-Straße in Prenzlau) umbenannt.
Quellen:
• Adreßbücher der Stadt Prenzlau in mehreren Jahrgängen
• Stadtpläne der Stadt Prenzlau und Umgegend aus mehreren Jahren
• "Die Prenzlauer Straßen und ihre Geschichte", Alfred Hinrichs, maschinenschriftliche Aufzeichnungen, 1954