Da kong Frederik den 4. anlagde Frederiksberg Slot i slutningen af 1600-tallet, fik han samtidig udarbejdet en plan for et haveanlæg.
Kongen havde tidligere haft en mindre lystgård ved Allégade, og imellem den og slottet, skulle haven anlægges.
Slottet kom til at ligge på toppen af den naturlige Frederiksberg Bakke og haven blev anlagt på bakkens skråning mod nord.
Planen til haveanlægget udformes formentlig af ingeniørofficeren Hans Heinrch Scheel (1668-178). Han lader havens ene akse gå fra den gamle lystgård til fasaneriet i den vestlige del, mens en anden går omtrent nord-syd, med slottet på bakken som det ene slutpunkt.
Det faldende terræn foran slottet kunne udnyttes til et terasseanlæg med fontæner og kaskader. Forbilledet var dels haveanlæg ved italienske villaer, som kongen havde besøgt, dels haven ved det fornemme franske slot Versaillies.
Vandet til kaskaderne kom fra Damhussøen og blev via Møllesøen i Valby pumpet op i et vandreservoir over slottets portbygning.
Hovedindgangen til parken er fra Frederiksberg Runddel, der markerer afslutningen på Frederiksberg Allé. Den fornemme boulevard var fra begyndelsen forbeholdt de kongelige, når de skulle fra København til slottet.
Senere blev den en promenadevej for københavnerne, når de skulle besøge Frederiksberg Have.
Parken blev fra begyndelsen åbnet for publikum, og folk valfartede herud for at få en chance for at overvære, når de kongelige sejlede på kanalerne.
Den oprindelige park var strengt symmetrisk anlagt, men i takt med de nye tendenser i havearkitekturen omkring år 1800, blev den omlagt til en landskabshave med slyngede stier, “tilfældigt” anlagte søer og overraskende momenter.
Også havens sydlige del, Søndermarken, fik et mere naturpræget udseende, selv om de faste akser blev bibeholdt.
Det store kaskadeanlæg foran slottet blev nedlagt, og vandet blev i stedet brugt til søer og kanaler.
Haven blev et populært udflugtsmål for københavnerne, som flokkedes på den såkaldte “smørrebrødsplæne” (herover). Tilstrømningen blev efterhånden så stor, at man måtte henvise de besøgende til kun at spise deres medbragte mad på bestemte steder, og tobaksrygning og barnevogne blev forbudt.
På en ø ved Andebakken, blev der omkring 1800 bygget et kinesisk lysthus efter tegninger af arkitekten Andreas Kirkerup (1749-1810).
På en anden ø blev lavet et kunstigt vandfald af sten, der kom fra byggeriet af Frederiks Kirke.
I den sydvestlige del af haven blev der omkring 1800 bygget et græsk tempel. Apistemplet var tegnet af Nicolai Abildgaard (1743-1809) og bestod af en forhal med seks søjler, der var blevet til overs ved ombygning af et af Amalienborg Slots palæer.
Templet var ikke bare til pynt, men kom også til at fungere som indgang til Zoologisk Have, der blev anlagt i denne del af Frederiksberg Have i 1859. Helt frem til 1970’erne kunne man komme ind i haven ad denne indgang.
Mod sydvest opførtes omkring 1800 et hus i schweizisk stil. Det blev ligesom Apistemplet tegnet af Nicolai Abildgaard. Huset symboliserede datidens længsel efter et liv i pagt med naturen, hvor den landlige ensomhed blev et ideal.
På den kunstige høj i havens vestlige del, for enden af den gamle hovedakse, opførtes en oldtidshøj. Herfra kan man se tværs gennem haven, for selv om de oprindelige alléer blev nedlagt, er sigtelinjen fra højen mod København dog bevaret.
En kunstigt anlagt “eremithytte” blev udstyret med en mekanisme, så en eneboer, der lå på en seng, rejste sig, når man gik ind i hytten.
Haven havde et fasaneri, hvor der blev opdrættet fasaner. Den tilhørende Fasangård (herover) blev tegnet af arkitekten Johan Cornelius Krieger (1683-1755) og blev opført omkring 1724. I 1828 blev bygning forhøjet med en etage.
Fasanavlen ophørte i 1785, men Fasangården er stadig bevaret. Den var i mange år hjemsted for bl.a digtere som Adam Oehlenschläger, men blev senere stedet hvor Gunnar Sadolins farvefabrik startede sin produktion.
Ved havens indgang mod Frederiksberg Runddel, står billedhuggeren H. V. Bissens statue af kong Frederik den 6.
I havens sydøstlige del står en statue af politiken C. Hall, der boede i den nærliggende Ny Bakkegård ved Bakkegårds Allé og Halls Allé.