Die Kremmener Eisenbahnlinie von Schönholz über Velten nach Kremmen wurde 1891 bis 93 eingleisig angelegt. Die Königliche Eisenbahn-Direktion zu Berlin errichtete das von dem königlichen Regierungsbaumeister Gareis entworfene Empfangsgebäude aus gelben Ziegelsteinen, dessen geringe Reste in dem heutigen, gewerblich genutzten Gebäude links vom Treppenabgang unsichtbar noch erhalten sind. Das ursprüngliche Empfangsgebäude bestand aus einem links (nördlich) gelegenen Teil, in dessen Obergeschoss sich die Dienstwohnung des Bahnhofsvorstehers Karl Wistuba (1847 – 1917) befand, und einem rechts gelegenen eingeschossigen Teil mit Betriebsräumen.
Zwischen beiden Teilen war zum Vorplatz ein in der Blickachse der Grußdorfstraße angeordneter dreigeschossiger  Turmbau mit einer großen Uhr eingefügt.
Gleichzeitig wurde rechts vom Treppenabgang die noch heute vorhandene gewerblich genutzte Wartehalle für den Ausfl ugsverkehr als Fachwerkbau mit Ziegelsteinausmauerung erbaut. Links (nördlich) vom Empfangsgebäude entstand noch ein – nicht erhaltenes – zweigeschossiges Dienstgebäude mit der „Bahnmeisterei 69“.
Nachdem am 01.08.1893 die Strecke von Schönholz bis Heiligensee für den Güterverkehr freigegeben war, dampfte am 01.10. desselben Jahres der von Schönholz kommende erste fahrplanmäßige Personenzug nach Velten in den Tegeler Bahnhof ein. Die Kremmener Bahnlinie begann aber nicht in Schönholz, sondern im damaligen Nordbahnhof, der in der Berliner Bernauer Straße auf dem Gelände des heutigen Mauerparks lag.
Erst seit dem 01.02.1898 fuhren die Züge vom Stettiner Bahnhof, dem jetzigen Nordbahnhof, ab. Von den anfangs täglich neun Zügen in jede Richtung fuhren sechs nur nach Tegel und drei weiter nach Velten, seit Ende 1893 bis Kremmen. Bis Tegel gehörte die Strecke zum Bereich des preisgünstigen Vororttarifs, so dass die Fahrkarte für eine einfache Fahrt von Berlin hierher in der zweiten Klasse 30 Pfennig und in der dritten Klasse 20 Pfennig kostete.
Als die Fahrgastzahlen wegen des gestiegenen Ausfl ugsverkehrs und der seit 1898 erfolgenden Ansiedlung von Fabriken in Reinickendorf und Tegel sowie wegen des Einzugs zusätzlicher Einwohner in die vielen Wohnhäuser in Tegel und Borsigwalde stark zugenommen hatten – schon 1898 fuhren an jedem Wochentag 36 Züge –, wurde 1903/04 die Strecke zwischen Schönholz und Tegel zweigleisig ausgebaut, wobei man zugleich die Gleise zwischen Schönholz und Borsigwalde auf den heutigen Eisenbahndamm hochlegte. Nur im Tegeler Ortskern blieb der ebenerdige Verlauf der Gleise bis heute erhalten.
Auch der Bahnhof Tegel wurde um 1904 ausgebaut. Da die Eisenbahnverwaltung seit 1899 auf der Kremmener Bahn sowohl Fernzüge, die zwischen Gesundbrunnen und Tegel nicht mehr hielten, als auch Vorortzüge bis Tegel, die an jedem Zwischenbahnhof hielten, eingeführt hatte, errichtete man in Tegel einen zweiten Bahnsteig, der dem Fernverkehr von Berlin nach Velten und bis Wittstock diente. Als hier nur noch wenige Fernzüge hielten, wurde der zweite Bahnsteig mit Ablauf des 28.06.1933 geschlossen und anschließend beseitigt. Seitdem wird der einstige Treppenaufgang vom Fußgängertunnel zu diesem Bahnsteig als Bahnhofsausgang in Richtung Neu-Tegel und Borsigwalde genutzt. Der noch heute vorhandene erste Bahnsteig wurde damals an der Ostseite verbreitert, was an den nicht verbreitertem Bahnsteigdach erkennbar ist.
Seit dem 16.03.1927 dient der Bahnhof – mit Unterbrechungen 1945 und 1984/95 – als Station der elektrifi zierten Bahn, die seit 1930 „S-Bahn“ genannt wird.