Fréjusin kohdalla sijainneella rannikkotasanteella sijaitsi aikoinaan [[keltit|kelttiläis]]-[[liguurit|liguurilainen]] [[oppidum]]. Vuonna 49 eaa. [[Julius Caesar]] perusti paikallerpaikalle ''Forum Julii'' nimisen siirtokunnan, joka laajeni myöhemmin tärkeäksi sotilastukikohdaksi sillä se sijaitsi [[Via Aurelia]]n varrella. Kaupunki kuitenkin menetti merkitystään keskiajalla ja [[merovingit|merovingilaiselta]] tai [[karolingit|karolingilaiselta]] ajalta kaupungista ei ole juurikaan säilyneitä tietoja. [[Saraseenit]] tuhosivat kaupungin vuonna 940 ja sen asukkaat pakenivat. Asukkaat tulivat kuitenkin myöhemmin takaisin ja kaupungin ympärille rakennettiin muuri. Riculfe-niminen piispa avusti kaupunkia uuden katedraalin rakentamisessa ja kun satamakin korjattiin kaupunki kehittyi merkittäväksi kauppakaupungiksi. Kauppa kuitenkin hiljeni jo 1300-luvulla. Taantumiseen vaikutti yhtenä tekijänä [[rutto]]. Fréjusissa oli piispanistuin vuodesta 374 vuoteen 1957, jolloin se siirrettiin [[Toulon]]iin.<ref>Bennewitz, Cacoveanu, Kurtz, Mehling ja Summerer 1984, s. 88</ref>