Im April 1865 begann der Bau der Ostbahnstrecke Berlin- Küstrin. Am 1. Oktober 1867 erfolgte die feierliche Eröffnung der Küstriner Bahn im Berliner Ostbahnhof. Sie unterstand - wie die gesamte Ostbahn - der Ostbahn-Direktion Bromberg.
Die erste Fahrt am 1. Oktober 1867 war gratis. Es ist sogar eine Frau aus Fredersdorf mitgefahren. Jedoch gab es noch keinen Bahnhof in Fredersdorf. Da die Ostbahn als Fernbahn angelegt wurde, entstanden nur wenige Bahnhöfe an der Strecke.
Erst am 15. September 1872 wurde die Haltestelle Petershagen/Ostbahn innerhalb der Gemarkung Fredersdorf eingerichtet.
Ab 1. Januar 1875 wurde der bisherige Stationsname Petershagen in Fredersdorf Ostb. geändert, ohne dass eine Verlegung des Bahnsteigs notwendig wurde. Den Anlass bildete freilich ein amtlich so genanntes "Vorkommnis" aktueller Natur. Auf der Station hatte es 1874 einen Verletzten gegeben. Da sich trotz des Stationsnamens Petershagen die Gemeinde Petershagen für die Versorgung des Betreffenden nicht zuständig fühlte, sondern Fredersdorf verantwortlich gemacht wurde, kam die Umbenennung ins Rollen.

Im Jahre 1875 wurde auch das Beamten-Wohngebäude (heute Bahnhofstraße la u. 1b) fertig gestellt. Die Haltestelle wurde in einem bahnhofsähnlichen Zustand versetzt. Gleise wurden erweitert, die Pflasterung der Ladeplätze erfolgte und Bahnsteig und Gleisanlagen wurden eingezäunt. Der Bahnsteig befand sich gegenüber dem Gebäude der Sparkasse.

1882 wurde neben dem Fernverkehr ein offizieller Vorortverkehr eingerichtet. Die Vorortzüge benutzten ebenfalls die Fernbahngleise. Erst nach der Jahrhundertwende entstanden in Fredersdorf Bahnhofseinrichtungen: ein Stationsgebäude, Wartesäle, Schuppen für Ladegut und Gepäckstücke, Geräteschuppen und ein Abort für Männlein und Weiblein mit Grubenanschluss. Alle Gebäude waren aus Holz und trugen barackenähnliche Pultdächer.
Daraufhin erfolgte die Einstufung der Station Fredersdorf zum 1. April 1905 zu einem "Bahnhof II. Klasse der Königlichen Ostbahn". Mit der höheren Einstufung war eine bessere personelle Besetzung verbunden. Zu Zeiten Robert Pfennigs als Bahnhofsvorsteher zählte das ihm unterstehende Personal des Bahnhofs 12 Personen.

Das Bahngelände von Fredersdorf wurde 1943 aufgeschüttet. Es entstand ein neuer Bahnsteig an dem heutigen Standort. Entlang der Ostbahn wurde der Gleisbau für die Vorortbahn im Mai 1943 erneut aufgenommen, und von Berlin aus viergleisig ausgebaut, um Fern- und Militärzüge rasch durchschleusen zu können. Um sie anzulegen, wurde Straßengelände im Anschluss an das Bahngelände, von der Bahnhofstraße, der Voigtstraße und der Straße an der Bahn weggenommen.

Am 11.April 1944 wurde die Vorortstrecke zwischen den S-Bahnstationen Berlin-Mahlsdorf und Strausberg eröffnet. Der Bahnhof Fredersdorf entstand als S-Bahnstation Fredersdorf bei Berlin. Die S-Bahn-Strecke zwischen Mahlsdorf und Strausberg war aber noch nicht elektrifiziert, sondern wurde mit Dampfloks betrieben. Diese "S-Bahn-Züge" hießen im Volksmund Schwarzer Zug". Zwischen Fredersdorf und Neuenhagen entstand 1944 der "Haltepunkt Fredersdorf-Verschiebebahnhof'. Fredersdorf hatte damit zwei Bahnhöfe. Der neue Fredersdorfer Verschiebebahnhof, den es nicht mehr gibt, lag etwa 300 Meter hinter der Sportstätte Radrennbahn und wurde nicht nur von den Eisenbahnern, sondern auch von vielen Fredersdorfern genutzt. Kriegsbedingt waren auch mehrere Umbaumaßnahmen am Fredersdorfer Bahnhof, vorgenommen worden, die 1943 und 1944 stattfanden. Der Güterbahnhof Fredersdorf wurde auf die südliche Seite des Bahnhofsgeländes verlegt, um für das S-Bahnhofsgebäude Platz zu schaffen. Die gepflasterte "Lade-Straße" auf der Südseite, die es noch heute gibt, wurde angelegt. Für den Güterbahnhof wurde das heute noch stehende feste Haus mit erhöhter Laderampe errichtet.

Am 20. April 1945, in den letzten Kriegstagen ist das Bahnhofsgebäude beim Herannahen der sowjetischen Truppen von der SS-Division "Nordland" gesprengt worden. Nach 1945 wurde an gleicher Stelle das heutige Bahnhofsgebäude (als solches nicht mehr genutzt und privatisiert) errichtet. 1946/1947 werden die zweiten Gleise der Fernbahn, wie auch der S-Bahn von der sowjetischen Besatzungsmacht demontiert.

Am 1. September 1948 wird die bisher dampflokbetriebene S-Bahn-Strecke Hoppegarten - Fredersdorf an das elektrifizierte S-Bahnnetz angeschlossen. Im Oktober 1948 erfolgt die Anschluss-Elektrifizierung von Fredersdorf bis Strausberg.

1975 findet ein Festumzug zum 100. Jahrestag des Fredersdorfer Bahnhofes statt. 1988 wird die neue Stahlbrücke des Bahnhofes eingeweiht.

Und endlich, am 3.12.2004 erhält Fredersdorf den seit vielen Jahren angestrebten Südzugang zum S-Bahnhof mit drei behindertengerechten Zugängen.