Allehelgenskirken, første gang nevnt i skriftlige kilder som Allra heilagra kirkja 1181, en trekirke som lå på sørvestsiden av den daværende Vågsbunnen, omtrent der Det annekterte rådhus (hjørnet Allehelgens gate/Rådstuplass) nå ligger. Etter at den brant 1248, lot Håkon Håkonsson bygge en steinkirke på stedet, fullført av Magnus Lagabøte 1266. I 1276 ble det opprettet et hospital med 30 senger for fattige menn i tilknytning til kirken; fra 1308 var kirken kongelig kapell. Hospitalet hadde setstove og sovestove, men ser ut til å ha forfalt etter Svartedauden. Det var flere branner i Vågen-området på 1400-tallet, og det er ikke kjent når kirken brant. Men birgittinerne, som hadde overtatt Munkeliv klosters eiendommer, søkte om å få flytte inn i Allehelgenshospitalet 1442. Absalon Beyer nevner 1565 det høye kirketårnet og kirkegården. Da hadde det imidlertid i 1552 vært gitt tillatelse til å bruke rester av kirkemurene til nytt rådhus. De ble i stedet brukt til fyllmasser over et myrområde langs Vågen for å få forbindelse til Domkirken (Domkirkegaten). I 1559 blir Allehelgenskirken omtalt som «den øde kirke». Det meste som stod igjen, forsvant etter brannen 1623. Kjelleren hadde da vært brukt som fangehull; de siste ruiner tjente en tid som øllager. Rester av forgylt kobber ble funnet 1865, trolig fra et relikvieskrin, og finnes nå i Historisk museum.
Se også oversikt over Bergens middelalderkirker.