Under slutet av stenåldern (cirka 2300-1800 f Kr) började det område som i dag är Kungliga nationalstadsparken stiga ur havet. Landskapet liknade dagens ytterskärgård. Troligen vistades människorna här mer tillfälligt, för att jaga och fiska. De första spåren är några stenyxor, funna vid Ulriksdal. Under bronsåldern (1800-600 f Kr) låg stranden cirka 15 meter högre än i dag. Öarna hade blivit större men det var fortfarande ett ganska kargt skärgårdslandskap med dåliga möjligheter att bo permanent. På några höjdpartier inom parken finns röseliknande gravar som kan vara från denna tid.
Det var först under järnåldern (400 f Kr – 1050 e Kr) som området blev fast befolkat och man började bedriva jordbruk. Brunnsviken avsnördes från Saltsjön och blev en insjö. Ett tiotal järnåldersgravfält har påträffats inom parken. Under vikingatiden (800 – 1050 e Kr) skedde en stor befolkningsexpansion i hela Stockholmsområdet. Eftersom gravfälten vanligen låg i närheten av bebyggelsen kan vi förmoda att det vid denna tid fanns ett tiotal byar eller större gårdar i området.
