Die Arbeiten wurden überwiegend durch das Großunternehmen Funke & Schürenberg ausgeführt. 1871 war die etwa 1500 Plätze bietende Pauluskirche schließlich fertiggestellt, so dass am 28. Februar 1872 die Einweihung folgte.