Aarhus var gennem middelalderen præget af magtbalancen mellem konge, biskop og borgerne. En kongeborg blev aldrig opført i Aarhus, men i tidlig middelalder var byen overordnet set en kongelig magtbastion i samspil med en kongsgård og flådefaciliteter ved Viby. Efter den norske konge Harald Hårderådes overfald på byen i 1050 blev bispesædet genetableret ca. 1060, og en domkirke viet til Sankt Nikolai blev opført ca. år 1100. Den blev lagt uden for volden, hvor en ældre forgænger kan have ligget. På dette sted ligger i dag Vor Frue Kirke og Kloster.
Det var især etableringen af en række gejstlige institutioner, der prægede udviklingen i 1000- og 1100-tallet. Foruden domkirken var der mindst to mindre kirker, Sankt Oluf i byens nordlige ende i nuværende Mejlgade og Vor Frue i den vestlige ende af byen ved den nuværende Mølleparken. Begge blev bygget i 1100-tallet. Senere kom der helligåndshus (hospital) ved Immervad og en Sankt Karensgård for spedalske ved Grønnegade. Inde bag volden lå sandsynligvis »trækapellet ved havet«, der omtales i anden halvdel af 1100-tallet.
Bebyggelsen i 1000-tallets sene del og i 1100-tallet har kun efterladt sig svage spor. Der er påvist spor af bebyggelse både inden for og uden for det voldomkransede areal, og det står klart, at volden heller ikke i den tidlige middelalder markerede byens fysiske grænser. De skal i stedet søges nordligere og vestligere ved Nørregade/Nørrebrogade og Vesterport. Ved udgravninger på Bispetorvet er fundet bebyggelse og smedevirksomhed, mens der er påvist en række brønde på Store Torv og rester af huse i Rosensgade og Guldsmedgade. En række brønde i Vestergade vest for Grønnegade antyder, at bebyggelsen har spredt sig hertil. Omkring og især vest for Vor Frue Kirke er der fundet gruber og andre bebyggelsesspor fra 1000- og 1100-tallet, så det er sikkert, at et bykvarter har ligget her.
Størstedelen af vikingetidens gadenet blev videreført i tidlig middelalder. En ny, stenbrolagt gade erstattede den træbrolagte gade langs voldens inderside, og også Kannikegade fik stenbrolægning. I samme tidsrum kom Domkirkepladsen og Rosensgade til. Mejlgade og Skolegade eksisterede i 1100-tallet ligesom den vestlige udfaldsvej nord for Vor Frue. I syd var byen endnu afgrænset af åen.
Byens tidligmiddelalderlige havn lå formentlig ligesom den vikingetidige havn på holmens sydside. Dele af byens højmiddelalderlige åhavn er påvist: Fundene består af nedrammede pæle med tilhørende fletværk på nordsiden af åen ganske tæt på den senere Skt. Clemens Bro.
Tiggerklosterbevægelserne, der med stor hastighed bredte sig over hele Europa i 1200-tallet, nåede med munke fra dominikanerordenens ankomst i 1220’erne også til Aarhus. Aarhusbispen overdrog den gamle domkirke til dem, og i løbet af høj- og senmiddelalderen ombyggede de den til et firfløjet klosteranlæg. Støttet af donationer fra Aarhusbispen blev der også opført et karmelitermunkekloster i byen i 1400-tallet. Begge blev nedlagt ved Reformationen.
Byens gadenet undergik ca. 1253‑68 en større omlægning, sandsynligvis igangsat af Aarhusbispen, der samtidig var i gang med de omfattende byggearbejder på domkirkekomplekset. Ved omlægningen blev store bebyggelsesområder inden for volden ryddet for at skabe plads til anlæggelsen af Store Torv, og uden for volden blev Lille Torv og Immervad, der fører ned til åen, anlagt ved, at det fugtige område vest for holmen blev fyldt op. En portbygning, som stod frem til 1683, blev formentlig også opført ved Borgporten på denne tid. Vestergade, vest for Lille Torv, løb ud til Vesterport, hvor Aarhus Mølle i 1289 nævnes beliggende. Anlæggelsen af møllen var forbundet med en stor mølledam og dæmning hen over ådalen. Guldsmedgade, der løber fra Lille Torv mod nord, og Klostergade, der strækker sig fra Studsgade i øst til Grønnegade i vest, blev også anlagt i slutningen af 1200-tallet eller begyndelsen af 1300-tallet. I begyndelsen af 1300-tallet bredte bebyggelsen sig over åen ved Immervad. Fundet af et gørtlerværksted fra ca. år 1300 antyder dog, at området ikke var ret tæt bebygget, for erhvervet var forbundet med brandfare.
I løbet af højmiddelalderen samlede biskoppen større og større magt hos sig og blev sammen med domkirkens præsteskab Østjyllands største godsejer. Pestepidemierne i anden halvdel af 1300-tallet bortrev en stor andel af befolkningen, hvilket dog gav de overlevende, afgiftsbetalende bønder bedre betingelser. Borgernes råderum var indskrænket. Det er uvist, hvornårAarhus fik sin første stadsret, men det skete før år 1300, og et bysegl, kendt fra et aftryk, stammer fra ca. 1250.
Byens borgere opførte det første kendte rådhus midt på Store Torv i begyndelsen af 1300-tallet. Rådhuset tilhørte byen, men torvet tilhørte bispen, og betalingen af grundskyld fra by til domkapitel var årsag til konflikt mellem by og bisp. Byen husede også en offentlig badstue, der var i brug frem til 1500-tallet, og som menes fundet på hjørnet af Lille Torv og Badstuegade i 1908.
I senmiddelalderen spredte bebyggelsen sig syd for åen langs Fiskergade, og den sydlige udfaldsvej førte via en bro ved Immervad op mod Brobjerg, hvor byens karmeliterkloster kom til i 1480’erne. I 1477 var der også givet tilladelse til, at voldterrænet mellem Immervad og den sydlige port tættest på kysten kunne blive bebygget, mens den vestlige vold, og efterfølgende også den nordlige voldstrækning, blev udlagt til bebyggelse 1512‑13.
På samme tid blev arealet langs åens sydside også inddraget i havnearealet. En større arkæologisk udgravning langs Fiskergades nordside har givet indblik i konstruktionen af havnen på en ca. 200 m lang strækning fra Immervad i vest til Skt. Clemens Bro mod øst. Åhavnen var konstrueret af nedrammede pæle med fletværk imellem, som blev holdt sammen af opfyldninger mellem åbrink og fletværk. Det ældste bolværk er dateret til ca. 1442, og mellem dette tidspunkt og slutningen af middelalderen blev bolværkerne bygget ud i åen i alt seks gange. De gentagne udbygninger vidner om åens tiltagende tilsanding. Det påhvilede den enkelte grundejer at vedligeholde bolværkerne, men mange grundejere forsømte dette, hvilket gav anledning til utallige konflikter mellem borgere og byens administration. Den manglende vilje til at bruge ressourcer på vedligeholdelsen afspejler sig tydeligt ved, at bolværkerne er opført af forskellige udtjente materialer, bl.a. genbrugte dele af nedbrudte bygninger og udslidte skibe. Efterhånden som skibenes dybgang øgedes, blev trafikken på åen domineret af pramme.
Jens Iversen Lange, der var biskop i årene 1449‑82, fuldførte domkirkens forvandling til en gotisk katedral. Med ham kulminerede embedets magt. Han fik Kalø Len med den vigtige fæstning i pant, vistnok personligt, i ca. 1467. Siden 1450’erne havde han også været lensmand over Aarhus købstad som pant for en gæld, kongen havde til ham. Byens skatter tilfaldt derfor biskoppen. Handel og håndværk var overvejende lokale, men fund af keramik og klædeplomber viser kontakter rundt om Østersøen og til Nordvesteuropa siden tidlig middelalder.
Borgernes vilkår blev bedre i 1400-tallet, og håndværk og handel blev nu specialiserede erhverv med gode indtægter fra Skånemarkedet og hansestæderne, og et smedelav omtales første gang i 1493. I 1441 blev der udstedt forbud mod handel i småhavnene. Borgerne optrådte med større selvsikkerhed over for biskoppen, da oksehandelen gik frem i slutningen af 1400-tallet.
Flere møntskatte indeholdende handelsmønter af lav værdi til dagligdags brug afspejler byens senmiddelalderlige handelsnetværk. Den største skat på næsten 6.000 mønter, fundet ved Lilletorv, var ca. år 1400 blevet gemt væk i en stentøjskande. Kanden indeholdt mønter fra Hamburg, Lüneburg, Wismar og Rostock og må opfattes som en regulær »bankboks«, idet disse mønttyper er overordentlig sjældne som enkeltfund i byen. Den vidner om, at det var muligt for i alt fald én borger, sandsynligvis en købmand, at oparbejde en meget stor formue i senmiddelalderens Aarhus.