De første anmodninger om koncession på anlæg af en jernbaneforbindelse mellem København og Frederikssund fremkom i 1869. Selve loven om jernbanens oprettelse blev vedtaget i lov af 23. maj 1873, dog ændret ved lov af 24. maj 1875. Den 11. maj 1876 udstedtes koncessionen til Det sjællandske Jernbaneselskab. Arbejdet skulle være færdigt inden 1. oktober 1878, men fristen blev senere forlænget, fordi jordarbejdet i forbindelse med anlæg af dæmninger over mosedrag trak i langdrag. Således f. eks. ved Hellede mose, hvor der blev arbejdet i halvandet år, og hvor store dele af dæmningen flere gange forsvandt i mosen.

Strækningen, der udgik fra Vestbanen ved Frederiksberg station, var klar til officiel indvielse den 15. juni 1879, og den 17. juni begyndte den regelmæssige drift med tre tog daglig i hver retning et persontog og to blandede tog.

Ved de sjællandske baners overgang til staten (lov af 2. juli 1880) blev Frederikssundbanen statsbane.

I forbindelse med anlægget af Københavns tredie hovedbanegård anlagdes strækningen Valby- Vanløse, og togene til og fra Frederikssund førtes denne vej fra og med den 1. december 1911. Elektrisk drift indførtes på ovennævnte strækning den 23. september 1941, og Vanløse blev herefter Frederikssundbanens endestation. En yderligere afkortning skete den 15. maj 1949, da elektrificeringen nåede Ballerup. 2. spor åbnedes for drift på strækningen Frederiksberg-Vanløse den 20. maj 1932, Valby-Vanløse den 23. september 1941 og Vanløse-Herlev den 26. april 1949. Inden for en overskuelig årrække må det påregnes, at hele den resterende strækning Ballerup-Frederikssund vil overgå til elektrisk drift.

Samtidig med åbningen af den midtsjællandske banes 3. sektion (Hvalsø-Frederikssund) den 17. november 1928 blev sidstnævnte bys nuværende banegård taget i brug. Beliggenhed er - og har altid været ret uheldig, så en tilbageflytning til den oprindelige stations areal (den nuværende godsstation) er nær forestående. (EBJ).