Medeltidsstaden, senare benämnd Gamlebyen, utgjorde det ursprungliga Oslo. Den utgör idag kärnan i dagens stadsdel Gamle Oslo. Oslo var Norges huvudstad från 1300 och var en av de största städerna i Norge fram till stadsbranden 1624, då staden brann ned. Därefter beslöt kungen av Danmark-Norge, Kristian IV, att den skulle återuppbyggas på en ny plats väster om Björvika. Den nya staden fick namnet Christiania, senare stavat Kristiania, medan namnet Oslo användes för det nedbrända området, som i huvudsak återgick till jordbruksmark.
Enligt Snorres kungasaga grundlades köpstaden Oslo omkring 1048 av Harald Hårdråde, men vid arkeologiska utgrävningar på 1970-talet visade det sig att Oslo hade en stadsstruktur redan omkring år 1000. År 1070 blev Oslo biskopssäte. Stadens domkyrka, Hallvardskatedralen, uppfördes på höjden vid Oslo torg i början av 1100-talet. Oslo katedralskole grundades 1153.
Invånartalet fördubblades under högmedeltiden till ungefär 3 500. Perioden närmast före och närmast efter 1300 var medeltidsstaden Oslo som störst. Håkon Magnusson, som var hertig över Øst-Norge mot slutet av 1200-talet, igångsatte en rad byggaktiviteter, bland annat utvidgades Mariakirken och påbörjades uppförandet av Akershus slott. Då Håkon skulle överta kungakronan 1299 efter brodern Erik Magnussons död, valde han Oslo som kröningsstad. År 1314 centraliserades makten till Oslo, bland annat genom att prästen i Mariakirken utnämndes till Norges rikes kansler, som fick i uppdrag att bevara kungens sigill och vara ordförande i Riksrådet.
Medeltidstaden drabbades av återkommande bränder. Bland annat plundrades staden och brändes ned av hertig Erik av Södermanland 1308. Den ännu inte färdiga fästningen stod emot belägringen, och staden byggdes upp igen på de tidigare tomterna. Under digerdöden minskade invånarantalet med omkring en tredjedel. Under åren med Norge som dansk provins från 1536, i union med Danmark, förlorade staden sin huvudstadsstatus och stagnerade ekonomiskt.
Under den svenska belägringen 1567 satte borgarna själva staden i brand, för att senare bygga upp den igen.