Ensimmäiset nykyisen Norjan alueelle ilmestyneet ihmiset putkahtivat esiin esihistorian hämäristä, kun mannerjäätikkö vetäytyi Skandinavian yltä. Kymmenentuhatta vuotta sitten nykyisten norjalaisten esi-isät metsästivät poroja ja muuta saalista pitkällä vaelluksellaan pohjoiseen. Maa, johon he tulivat, oli vuosisatojen ajan kantanut jääpeitteen painoa yllään, joten meri huuhteli rannikkoa 200 metriä korkeammalla kuin nykyään. Vanhin todiste ihmisen toiminnasta on löydetty mäeltä Østfoldin läänin kaakkoisalueelta, melko läheltä Ruotsin vastaista etelärajaa. Siihen aikaan kyseinen mäki oli todennäköisesti aivan jäätikön kärjen eteläpuolella sijaitseva rannikkosaari.
Mistä esi-isät nykyiseen Norjaan tulivat tai mitä reittejä he pohjoiseen matkasivat – siitä ei olla täysin yksimielisiä, mutta on melko varmaa, että yksi noista reiteistä kulki Østfoldin kautta. Siellä sijaitsevista asuinpaikoista löydetyt esineet ovat samantyyppisiä kuin ne, jotka on löydetty Etelä-Ruotsista ja Tanskasta. Toinen mahdollinen reitti on saattanut kulkea nykyisten Pohjanmeren valtioiden alueelta Lounais-Norjaan.
Ensimmäiset norjalaiset olivat metsästäjiä, jotka asuivat pienissä ryhmissä. Piikivestä valmistetut työkalut, saviastiat ja – ehkäpä kaikkein vaikuttavimpana – kalliokaiverrukset ovat merkkejä heidän olemassaolostaan. Käytännöllisesti katsoen kaikissa osissa Norjaa on säilynyt esimerkkejä heidän taiteestaan joko hakattuna tai raaputettuna kallioon. Kaiverrukset esittävät yleensä heidän saalistaan: poroja, hirviä, peuroja, karhuja ja kaloja. Harvinaisempia, mutta aivan yhtä vaikuttavia, ovat ihmisiä ja veneitä esittävät kuvat.
Siirtyminen maatalouteen alkoi Norjassa noin 5000–6000 vuotta sitten, aluksi Oslovuonoa ympäröivällä alueella. Etenkin Etelä-Norjasta tehdyistä pronssikauden (1500–500 eKr.) aikaisista arkeologisista löydöksistä suurin osa on maanviljelykulttuurin jäänteitä. Samalta ajalta peräisin olevat löydöt Pohjois-Norjasta osoittavat, että siellä asuneet ihmiset olivat metsästäjiä. Useista paikoista aivan pohjoisesta, Finnmarkista, löydettyjen metsästäjien laajojen asuinalueiden jäänteistä on löytynyt selkeitä todisteita ajoittaisesta yhteistyöstä monien yksilöiden kesken.
Rooman ajalta (0–400 jKr.) peräisin olevat hautalöydöt todistavat yhteyksistä eteläisiin sivilisaatioihin. Löytöihin kuuluu pronssisia ja lasisia tarve-esineitä sekä aseita. Myös kirjoitustaito riimukirjaimin tuli tuona aikana tunnetuksi
Pohjoismaissa.
Kansainvaellusaika 400–550 jKr. oli levoton jakso Manner-Euroopan historiassa ja Norjasta löydetyt esineet osoittavat, että samanlaiset olot vallitsivat myös Norjassa. Maatilojen olemassaolo reuna-alueilla osoittaa, että asutus oli saavuttanut täyden alueellisen ulottuvuuden. Siitepölyanalyysit paljastavat, että läntiset rannikkoalueet oli tuohon aikaan hakattu paljaiksi. Koska ajat olivat levottomat, heimot rakensivat puolustusjärjestelmiä, kuten esimerkiksi linnoituksia, joiden jäänteet erottuvat selvästi 50 km matkalla Norjan suurimman järven, Mjøsa-järven, itäpuolisilla rantapenkereillä.