Gamlestads församling bildades 1883 då den första territoriella församlingsindelningen genomfördes och omfattade dåvarande stadsområdet öster om Gullbergsån, dvs 12:e roten nr 1-19, Stora Olskroken samt 18-20 rotarna.

Med Gamlestads församling införlivades 1909 vissa delar av Kålltorp från Örgryte, 1928 vissa delar av Utby och Mellby byars skifteslag mm från Partille församling samt 1930 1/1 vissa hemmanslotter mm från Angereds församling. År 1951 1/1 överfördes Kålltorps och en del av Bagaregården till den nybildade Härlandaförsamlingen och samtidigt uppdelades Gamlestads församling i två kyrkobokföringsdistrikt: Gamlestads och Nylöse. År 1955 1/1 utbröts stadsdelen Kortedala ur Nylöse kyrkobokföringsdistrikt för att bilda ett särskilt Kortedala kyrkobokföringsdistrikt, vilket 1960 avskildes till egen församling.

S:t Pauli församling bildades 1969 1/1 och omfattar förutvarande Gamlestads kyrkobokföringsdistrikt inom Gamlestads församling samt de delar av Lunden och Gubbero, som då införlivades med församlingen från Örgryte och Kristine församlingar. Församlingen omfattar stadsdelen Olskroken samt delar av stadsdelarna Bagaregården, Gårda och Lunden.