De eldste deler av Domkirkens vestmur stammer fra en soknekirke – Olavskirken i Vågsbotn – som ble bygd allerede i 1100-årene. Omkring midten av 1200-årene ble kirken overtatt av fransiskanerne, som utvidet den og bygde sitt kloster på sørsiden. Kirkens kor med den tredelte koravslutningen ble bygd mellom 1270 og 1300. I dette koret ble kong Magnus Lagabøte gravlagt. Tårnfotens vestportal og de staselige grindverksvinduene fra 1270-årene vitner om at engelske håndverkere, eller nordmenn opplært i et engelsk byggemiljø, har arbeidet med kirken.
Kirken ble domkirke etter reformasjonen i 1537. Biskopen flyttet inn i klosteret og omdannet det til bispegård. Omkring år 1600 ble et sideskip bygd til kirken på sørsiden. Omtrent samtidig ble det nåværende tårnet bygd opp over vestre del av den gamle langkirken.
Kirken har brent flere ganger, både i middelalderen og etter reformasjonen. Etter den store bybrannen i 1702 ble den kraftig ombygd. Den fikk nytt sideskip med arkaderekke mot hovedskipet, og hvelvene i koret ble revet. I 1880-83 ble kirken restaurert og fikk sitt nåværende nygotiske interiør.