thumb|250px|Akershus festning ble påbegynt av Håkon Magnusson. Deler av de gamle strukturene er fortsatt synlige
Oslos historie kan deles inn i ulike faser. Byen var i mange år i skyggen av handelsbyen Bergen og erkebispesetet i Nidaros, selv etter at kong Håkon V Magnusson gjorde Oslo til hovedstad i 1314. Byen ble ikke landets største før ved den kraftige ekspansjonen på 1800-tallet.
Opprinnelsen Funn, herunder helleristninger og diabasbrudd for steinalderredskaper, tyder på at det har vært bosetninger innerst i Oslofjorden siden eldre steinalder, med livsgrunnlag i jakt og fiske. De eldste og fleste fortidsminnene befinner seg på Ekeberg, og peker i retning av det tidligere eikekledte høydedraget øst for Bjørvika som hovedstadens eldste bosetningsfelt. Fra bronse- og jernalder finnes kulturminner fra hele Oslo-området inklusive dagens nabokommuner. Området ser ut til å ha vært attraktivt. Senere funn tyder på tettere bosetning i Osloherad lenge før det vi nå regner som byens opprinnelse. Blant annet ble det på Teisen funnet en rekke verdisaker i 1844 som kan ha blitt gravd ned i urolige tider på 900-tallet.
Snorre Sturlason hevder i sine sagaberetninger at byen ble grunnlagt av Harald Hardråde rundt 1050 fordi det var godt med forsyninger der, og befolkningen var stor, slik at landet lett kunne forsvares derfra mot angrep fra Danmark, eller tjene som base for egne angrep mot Danmark – men utgravninger i Gamlebyen har påvist eldre kristne graver i et system som tilsier at det eksisterte en bystruktur før 1050. På denne bakgrunn feiret man byens tusenårs-jubileum i 2000.
Den første kongen som slo seg til her i noen særlig grad var Sigurd Jorsalfare, som også døde her 26. mars 1130. Han ble begravet i Sankt Hallvardskirken, som han selv hadde sørget for å reise. Kirken var oppkalt etter byens skytshelgen St. Hallvard. Etter kong Sigurds død og fram til borgerkrigene sluttet i 1240, ble byen stadig herjet av brann og plyndringer. Blant disse var kampene mellom kong Inge Krokrygg og Håkon Herdebrei i 1161, og kong Sverre Sigurdssons seier over baglerne i 1197. Særlig hardt var slaget, først på isen utenfor byen vinteren 1199, og senere inne i byen. Etter sammenstøt med grupperingene slittungene og ribbungene, klarte til slutt kong Håkon Håkonsson å etablere fred etter det avgjørende oppgjøret med hertug Skule i 1240.
Middelalderbyen Se også Middelalderbyen Oslo Det økonomiske grunnlaget for Oslo var byens rolle som havn og markedsplass. Det førte til at kirker ble anlagt tidlig, og at kongene tidvis hadde tilhold i byen og etter hvert utvidet og befestet Kongsgården som lokalt maktsentrum. Da den norske kirken ble organisert, ble Oslo det naturlige setet for biskopen på Østlandet. Det førte til oppførelsen av bispekirken, den romanske Sankt Hallvardskirken. I tilknytning til katedralen anla og befestet biskopene en residens som kunne måle seg med Kongsgården i størrelse og militær betydning. Her i dette kirkelige sentrum ble også dominikanernes kloster Olavsklosteret anlagt. I tillegg til disse monumentale murbygningene ble det reist ytterligere fem kirker og to klostre i eller ved byen, og i tillegg et kloster på Hovedøya.
thumb|Oslo ladegård ble anlagt på ruinene av den gamle bispeborgen etter at byen ble flyttet i 1624 Etter Magnus Lagabøtes død i 1280 ble styret delt mellom de to sønnene Eirik og Håkon. Eirik var formelt konge over hele landet, men broren Håkon ble hertug og fikk i realiteten selvstendig styring over sitt hertugdømme. Da Eirik døde uten sønner i 1299, ble Håkon konge for hele landet. Han fortsatte å ha fast tilhold i Oslo, og i 1314 gjorde han byen til landets hovedstad, da han bestemte at rikets segl skulle oppbevares av kansleren (landets administrative leder). Kanslerembetet ble fast knyttet til embetet som prost ved det kongelige kapell, Mariakirken, rett ved siden av kongsgården ved Alnaelvas utløp. Fra denne tiden var Oslo den byen der konger oftest oppholdt seg, selv om de norske kongene knapt oppholdt seg i Norge fra 1300 til 1905. Ifølge Hans Jacob Orning var Oslo i utgangspunktet en utkant i Norge. Harald Hårfagre var først og fremst en vestlandskonge, mens Viken (området rundt Oslofjorden) var trolig dansk. Både Sarpsborg og Oslo var på 1000-tallet militære utposter mot Sverige og Østlandet var også på 1100-1200-tallet et omstridt og lite integrert del av riket.Orning, Hans Jacob i Klassekampen, 13. oktober 2014.
Både kongens egen byggevirksomhet på Kongsgården og Mariakirken, og det faktum at byen nå ble et viktigere maktsentrum, bidro til byens vekst. I denne perioden var byen fortsatt preget av tett tømmerhusbebyggelse i én etasje. Etterhvert kom enkelte hus med to eller tre etasjer, og noen få private steinhus. Men kongens og biskopens monumentale anlegg, og de mange steinkirkene, var dominerende innslag i bybildet.
Utover høymiddelalderen økte byens befolkning fra rundt 2 000 til 3 500. Den var likevel langt mindre enn det viktige handelssenteret Bergen, som var minst to eller tre ganger så stor. Men Håkon Magnusson var i sin samtid en betydelig europeisk fyrste, internasjonalt orientert og med betydelig politisk kraft, noe som også gjorde at byen som kongssete ble stadig viktigere. Hans sterke religiøse forankring fikk ikke bare uttrykk i utvidelsen av Mariakirken, men også i det at han oppmuntret og støttet fransiskanernes klosteretablering i byen, der hvor Gamlebyen kirke og Oslo Hospital ligger i dag.
Både svartedauden og andre pestangrep, bybrannene og den minskende politiske betydning Oslo som hovedstad fikk etter at landet gikk inn i unioner med Sverige og Danmark, gjorde at byen utover mot reformasjonen var i forfall. Folketallet sank, og til slutt var Hallvardskatedralen den eneste kirken i bruk.
I første del av dansketiden ble byens betydning stadig mindre, og særlig etter reformasjonen i 1537, som knekte den norske kirkens selvstendighet og dens stilling som økonomisk maktfaktor. Politisk ble byen degradert fra hovedstad til provinsby etter at kongemakt og sentraladministrasjon flyttet til København. Men byen beholdt lenge noen hovedstadsfunksjoner. Den var sete for kanslerembetet og møtested for riksråd og kongehyllinger, så lenge disse institusjonene besto. Den fikk rikets myntverksted ved Akershus, og var fortsatt viktig som lokalt militært og kirkelig sentrum. Lensherren på Akershus innehadde landets viktigste embete og var tidvis kongens stattholder. Festningen erstattet kirkens institusjoner som byens økonomiske tyngdepunkt og største arbeidsplass.
Det bidro til å holde folketallet nede at byen med jevne mellomrom ble rammet av nye pestangrep, bybranner og militære angrep. Byen skal ha brent anslagsvis 14 ganger. I 1567 ble Oslo invadert av svenske tropper under Den nordiske syvårskrig. Da ble byen jevnet med jorden, dels av svenskene, dels av byens egen befolkning under ledelse av lensherre og stattholder Christen Munk, for å hindre at svenskene fikk et tilholdssted under beleiringen av Akershus festning. Byens befolkning bygget den hver gang opp igjen på sine gamle tomter, siste gang etter en brann i 1611. Men etter Bybrannen i Oslo 1624 gikk den driftige kong Christian IV hardt til verks og forbød borgerne å gjenreise hus på branntomtene. Bygrunnen ble utlagt til jordbruksarealer (Oslo ladegård) for å forsyne Akershus festning med mat og dyrefor.
Festningsbyen Christiania thumb|Christiania med Akershus festning og kvadraturen innenfor bymurene. Isaac van Geelkercks Christianiakart fra 1648, det nest eldste kjente kart over byen miniatyr|Reguleringsplan for byutvidelsen i 1657 med tre rekker kvartaler i Bjørvika. Kart av Willem Coucheron i Det Kgl. Bilbliotek, København Byen ble flyttet til motsatt side av Bjørvika på forterrenget til festningen, som skulle beskytte den og inngå i planen om å skape en moderne befestet by omgitt av voller med bastioner. Byplanen fulgte renessansens idealer om geometrisk orden, med rette og brede gater (24 alen eller 15 meter) i et rettvinklet system med store kvartaler. De største kvartalene med store tomter for rike kjøpmenn ble stukket ut ytterst mot havnen, langs den nåværende Dronningens gate. De mindre kvartalene øverst mot vest ble stykket ut i mindre tomter forbeholdt håndverkere og andre jevne borgere. Ved et av de høyest liggende gatekryssene ble torget anlagt, og her ble byens nye Hellig Trefoldigheds kirke og rådhus oppført. Der hovedgaten Kongens gate krysset byvollen, ble den viktigste av de tre byportene, Stadsporten, oppført.
Kongen bestemte allernådigst at byen skulle kalles Christiania etter ham selv. For å forhindre fremtidige branner ble det i prinsippet innført murtvang, men i praksis ble murhus bare påbudt for adel og formuende borgere. Mindre bemidlede innbyggere fikk lov til å bygge i utmurt bindingsverk. Begge byggemåter var imidlertid kostbare og fremmede for norsk byggeskikk. Det gikk derfor sent med gjenreisningen; mange trosset murtvangen og bygget ulovlige tømmerhus. Først etter en ny storbrann i 1708 ble murtvangen konsekvent gjennomført. Bindingsverk ble den mest utbredte byggemåten.
Kvartalene innenfor vollene var fullt bebygget rundt 1650, som Geelkercks kart viser. Behovet for nye byggetomter førte til den første byutvidelsen i 1657. Stattholder Niels Trolle tillot folk å bygge på oppfylt grunn ute i Bjørvika, mot at de selv bekostet fyllmasser og tiltak for å stabilisere grunnen. Ingeniøroffiseren Willem Coucheron utarbeidet en «reguleringsplan» for forlengelse av de øst-vest-gående gatene og anlegg av tre rekker kvartaler utenfor Dronningens gate. Hans kart viser eksisterende bebyggelse med kraftig rød strek og de nye kvartalene med tynnere strek. Denne utvidelsen ble langt på vei fullført før 1680. De ytterste kvartalene mellom Store og Lille Strandgate ble delvis bebygget før en brann i 1708 rammet dette strøket.Roede 2016, side 30–33.
Utenfor den egentlige byen («Kvartalerne») vokste det snart fram forsteder befolket av fattige som ikke hadde borgerskap og derfor ikke lovlig kunne drive egen næring, men som på forskjellige måter var økonomisk avhengige av byen. Forstedene, blant andre Vaterland i øst, Grensen og Sagene i nord, og Pipervika i vest, lå på byens territorium (Bymarken), men hørte i kirkelig henseende til Akerbygda, og var ikke omfattet av murtvangen og en del andre bymessige bestemmelser.
Vollene rundt byen ble oppgitt etter en brann i 1686, og byen fikk vokse nokså planløst utover forbi de gamle vollene. Etter brannen ble også Hellig Trefoldigheds kirke revet etter ønske fra de militære, som heller ville utvide festningen på byens bekostning. Den nye Vår Frelsers kirke ble oppført utenfor vollene og sto ferdig i 1699. Siste militære angrep mot byen kom i 1716, da Karl XII besatte selve byen, men ikke lyktes i å innta Akershus festning. Bebyggelsen fikk betydelig skade av festningens kanonild mot de svenske okkupantene. Først i 1784 ble byen formelt utvidet ved at de nærmeste forstedene utenfor vollene ble innlemmet.
Flyttingen medførte en viss vekst og framgang for byen, men den bevarte fortsatt preget av småby. Næringsgrunnlaget var handel, trelasteksport og byens rolle som garnisonsby. Da Christiania innenfor vollene var nær fullt bebygget omkring 1650, vokste innbyggertallet bare langsomt i de neste hundre år. Byggeaktiviteten var derfor beskjeden i tiden som fulgte. Men behovet for nye byggetomter mens vollene ennå besto, fremtvang allerede i 1657 den første byutvidelsen, da det ble åpnet for bebyggelse ved utfylling på strandgrunnen mot Bjørvika, mellom bryggene. Her ble etter hvert tre nye rekker med kvartaler anlagt før strøket brant i 1708.