St. Pauls kirke lå på oversiden av Nordnesgaten nær det nåværende krysset med Nordnesbakken. Kirken, en enskipet tømmerbygning med et smalere og lavere kortilbygg som var oppført 1716, ble innviet Allehelgens dag 1718 og var bekostet av Christian Dreyers enke Sophie Sem. Den brant ned til grunnen 1756, og ble ikke gjenreist. St. Pauls kirkegård omfattet kvartalet mellom Nordnesbakken, Bretterne, Tidemands gate og Nordnesgaten. Den ble anlagt 1650 for Nykirkens sogn som kirkegård for fattige og forbrytere, og var i bruk til 1856; 1890–91 ble den ryddet og utbygd med boliger.

Se også oversikt over Bergens middelalderkirker.