Die Hauptorte Brüssow, Strasburg und der Flecken Fürstenwerder mit Prenzlau sollten durch eine normalspurige Kleinbahn verbunden werden, die man in kreiseigener Regie betreiben wollte. 1901 wurde eine Konzession für die Errichtung einer Kleinbahn mit Lokomotivbetrieb für Personen- und Güterverkehr von Brüssow über Prenzlau nach Strasburg mit Abzweig von Dedelow nach Fürstenwerder erteilt. Robert Langbein wurde vom Kreis mit der Gesamtleitung des Bahnbaus beauftragt. Der im Sommer 1901 zwischen Prenzlau und Strasburg begonnene Bahnbau konnte im Herbst 1902 abgeschlossen werden. Die Gemeinden, durch deren Gemarkung die Bahn führte, hatten dem Kreis Prenzlau den dafür erforderlichen Grund und Boden unentgeltlich überlassen müssen. Die Arbeiten waren teilweise erschwert, da Höhenunterschiede, wie beispielsweise bei Ellingen, durch umfangreiche Erdarbeiten ausgeglichen werden mussten. Der Kreis Prenzlau war 1901 verpflichtet, alle Kleinbahnbaupläne in den betreffenden Kommunen öffentlich auszulegen. Die Baukosten der Prenzlauer Kreisbahnen wurden im Juli 1902 noch auf insgesamt 2.981.000 Mark beziffert. In der Schlussrechnung wurde diese Summe mit 4.509.461 dann deutlich übertroffen. Jeweils 1.089.747 hatten der preußische Staat und die Provinz Brandenburg als Beihilfe zur Verfügung gestellt, sodass der Kreis Prenzlau aus seinem Haushalt 2.329.967 Mark investieren musste. Der ursprüngliche Plan, die Kreisbahnstrecke zum Beginn der Zuckerrübenkampagne am 1. Oktober in Betrieb zu nehmen, konnte nicht realisiert werden. Erst vom 15. Oktober an fuhren täglich von Prenzlau aus nach Brüssow und Strasburg erste Güterzüge. Am 1. Dezember fand dann die offizielle Eröffnungsfeier statt, zu der Landrat von Winterfeldt u. a. auch den Königlichen Regierungspräsidenten von Moltke zu einer Sonderfahrt von Prenzlau nach Strasburg und einen Abstecher nach Fürstenwerder eingeladen hatte. Zunächst verkehrten noch gemischte Züge, die sowohl den Personen- als auch den Güterverkehr abdeckten. In der Zeit der Zuckerrübenkampagne wurden jedoch auch reine Güterzüge eingesetzt, um die nötige Transportkapazität zu erreichen. Da die 56 eigenen Güterwagen, die die Prenzlauer Kreisbahn damals besaß, oft nicht ausreichten, mietete man zusätzliche offene Waggons bei der Staatsbahn an. Allein im Monat November des Jahres 1903 musste die Kreisbahn über 1.000 Wagenladungen Zuckerrüben im Binnenverkehr abfertigen. Zu den Transportgütern gehörten aber auch Kartoffeln, Getreide, Baumaterialien und Vieh. Bis zu Beginn der 1930er Jahre beförderten die Kreisbahnen auch Post, die ein mitfahrender Beamter der Reichspost mit einem Bahnstempel entwertete (MACHEL u. BUCHWEITZ 2010). Die Strecke Prenzlau–Löcknitz gehörte mit täglich vier Zugpaaren zu den am stärksten frequentierten Linien. Nach mehreren Namensänderungen setzte sich in den 1930er Jahren die Bezeichnung „Prenzlauer Kreisbahnen“ durch. Die Ackerbürger-, Beamten- und Garnisonstadt Prenzlau, war von Anfang an auch der Betriebsmittelpunkt der Kreisbahnen. Hier entstand 1902 an der Ecke Stettiner Straße/Gartenstraße der Kreisbahnhof mit einem Empfangsgebäude, das 1928 umgebaut und erweitert wurde, so dass hier auch eine Gaststätte mit einer Weinstube, einer Bauernstube und einem Saal Platz fand.

Die 1915 errichtete Werkstatt der Prenzlauer Kreisbahn entsprach ebenfalls nicht mehr den Bedürfnissen. Deshalb wurde ¹⁹²⁷⁄₂₈ eine neue Hauptwerkstatt mit einem Lokschuppen nach Plänen des Architekten und Regierungsbaurates a. D. Josef Bischof an der Gartenstraße errichtet, die als einfacher Klinkerbau im Stil der neuen Bauhausarchitektur ausgeführt und am 28. Mai 1928 offiziell ihrer Bestimmung übergeben wurde (BECKERT 2008). Die Prenzlauer Kreisbahnen, die auch Reparaturwerkstätten unterhielten, beschäftigten 1939 etwa 160 Personen. Ihr Streckennetz konnte von 1902 bis 1915 von 84 km auf 97,4 km ausgebaut werden. Erst mit der 1945 beginnenden Teildemontage änderte sich dies. 1906 wurde mit der Eröffnung der „Kreisbahn Schönermark–Damme“, die verwaltungsmäßig der Prenzlauer Kreisbahn unterstand, auch Gramzow mit dem Schienennetz verbunden. Hier entstanden ein Empfangsgebäude mit Gastwirtschaft, ein großer Lokschuppen, Lokbehandlungsanlagen und ein Wohnhaus für die Bahnbeamten (ZUMPE 1991). Seit den 1920er Jahren entwickelte sich der Kraftfahrzeugverkehr zu einer ernsten Konkurrenz für die Kreisbahnen, die deshalb 1928 selbst acht neue Omnibuslinien im Kreis Prenzlau übernahmen, die nach Fürstenwerder, Bandelow, Zollchow, Wolfshagen, Woldegk (Mecklenburg–Strelitz) und Birkenhain führten. Damit entwickelte sich diese Region zu den verkehrsmäßig am besten erschlossenen in der Provinz Brandenburg. Nach dem Kriegsende 1945 ordneten sowjetische Offiziere im Zuge der Reparationszahlungen die Demontage der Kleinbahnstrecken an. Während die Strecken Prenzlau–Klockow, Schönermark–Damme, Damme–Brüssow und Falkenhagen–Fürstenwerder komplett abgebaut wurden, blieben die Strecken Brüssow–Löcknitz, Prenzlau–Kutzerow und Dedelow–Falkenhagen von der Demontage verschont. Auf Veranlassung des Prenzlauer Stadtkommandanten setzte Bürgermeister Kolb den bereits pensionierten Otto Bromann am 17. Mai 1945 zum „Chef des Eisenbahnwesens der Stadt Prenzlau“ ein, um die verbliebenen Strecken für den Verkehr zu ertüchtigen. An einer Beratung zur Wiederinbetriebnahme der Prenzlauer Kreisbahn nahmen am 6. Oktober 1945 der neu ernannte Leiter der Kreisbahn sowie der landwirtschaftliche Berater der Roten Armee, Herr Schulz und Herr Schicketanz von der Abt. Industrie und Handwerk teil (NIEPEL u. CZECHOWIAK 1987, S. 51). Im November 1945 waren in Prenzlau jedoch erst vier Dampflokomotiven, drei Personenwagen und ein Gepäckwagen betriebsfertig. Ca. 90 km vom Streckennetz waren demontiert worden. Erst im Dezember 1945 konnte der Zugverkehr auf den Strecken Prenzlau-Kutzerow und Dedelow–Falkenhagen wieder aufgenommen werden. 1946 begannen die von der SMAD befürworteten Arbeiten zum Wiederaufbau stillgelegter Kleinbahnstrecken. Noch im selben Jahr konnten die Strecken Falkenhagen–Fürstenwerder, Kutzerow–Strasburg, Prenzlau–Klockow, Prenzlau–Brüssow, und Brüssow–Löcknitz wieder in Betrieb genommen werden.

Ein Jahr später folgten die Strecken Damme–Gramzow, und Gramzow–Zichow, die der Kreisbahn Damme–Schönermark zugeordnet waren. 1948 folgte die Strecke Zichow–Briesenbrow und 1949 die Strecke Briesenbrow–Schönermark. Am 1.4.1949 wurde die Kreisbahn der Deutschen Reichsbahn zugeordnet. 1951 wurden Abfahrt und Ankunft der Kleinbahn auf das Gelände des Hauptbahnhofs verlegt, sodass das Gebäude der Kleinbahn nur noch der Unterbringung der Verwaltung diente. Durch das sinkende Verkehrsaufkommen mussten in den Folgejahren immer mehr Abschnitte der Kreisbahnen geschlossen werden. So u. a. die Strecke Prenzlau–Klockow (1972), Prenzlau–Fürstenwerder (1978) und Prenzlau–Löcknitz (1991), bis 1995 der Personenverkehr der Prenzlauer Kreisbahn komplett eingestellt wurde.