Pôvodne boli najstaršie stopy ľudského osídlenia na území dnešného Paríža objavené v roku 1991 pri stavebných prácach v štvrti Bercy na ľavom brehu bývalého ramena Seiny. Pozostatky osady zo 4. a 3. tisícročia pred Kr. skrývali monoxyl, šíp a luk a kostené a kamenné nástroje.
V roku 2008 bol uskutočnený archeologický objav, ktorý posúva najstaršie osídlenie až do obdobia mezolitu (8000 - 6500 pred Kr.). Neďaleko Seiny boli na predpokladanom brehu bývalého riečneho ramena v 15. obvode v ulici Rue Henry-Farman oproti parížskemu heliportu objavené pozostatky lovcov a zberačov. Miesto bolo opätovne osídlené i v neskorších dobách, v neolite a mladšej dobe železnej.
Okolo roku 300 pred Kr. sa na ostrove v Seine usadili Galovia z kmeňa Parisov, ktorí založili oppidum nazvané Lutetia (po slovensky Lutécia, po francúzsky Lutece; čiže „barinaté miesto“), respektíve Lutetia Parisiorum. Tradične býva za tento ostrov považovaný ostrov Cité.
Archeologické prieskumy v rokoch 1994 - 2005 ale túto teóriu narušili. Objav veľkého opevneného priestoru o rozlohe 15 ha na území dnešného mesta Nanterre spochybňuje význam hlavného osídlenia na ostrove Cité v dobe pred rímskou nadvládou.
Z 1. storočia pred Kr. sa zachovali zlaté mince (statéry), ktoré Parisiovia razili, a tiež prvá písomná zmienka o Lutetii, ktorú zanechal Gaius Iulius Caesar z roku 53 pred Kr. vo svojich Zápiskoch o vojne galskej, kde i stručne charakterizoval, že ich mesto leží na ostrove. V máji 52 pred Kr. sa uskutočnila pri Lutetii bitka v ktorej zvíťazil Ceasarov vojvodca Titus Labienus nad galskými kmeňmi Aulerkov, Senonov a Parisiov. Galovia radšej zničili mosty a vypálili vlastné mesto než by ho prenechali Rimanom. Tí však neobnovili sídlo na ostrove, ale založili nové centrum na južnom, ľavom brehu Seiny, ktorému dali tradičný rímsky pravidelný pôdorys. Oblasť okolo rieky, najmä na severnom, pravom brehu bola veľmi močaristá a územie ponúkalo len niekoľko málo pevných miest. Na juhu naopak vystupovalo návršie (dnešný Montagne Sainte-Genevieve) na ktorého vrcholku sa nachádzalo centrum novej Lutetie.