Aus diesen Gebets- und Bibelkreisen entwickelte sich im Lauf von Jahren eine „apostolische“ Bewegung, die später die Katholisch-Apostolische Gemeinde genannt wurde. Ab 1832 wurden Apostel durch Propheten berufen. Die Katholisch-Apostolische Gemeinde suchte, die gesamte Christenheit unter der geistlichen Führung der neu berufenen Apostel zu vereinen. Doch ihre Bemühungen stießen insgesamt auf wenig positive Resonanz; die Katholisch-Apostolische Gemeinde sah sich daher gezwungen, parallel zu ihren ökumenischen Bestrebungen eine eigene Kirchen­struktur mit einem eigenen Amtsverständnis und eigener Liturgie zu entwickeln.

Auf Grund von Meinungsverschiedenheiten über einzelne Auslegungen der Heiligen Schrift und die Berufung neuer Apostel kam es 1863 zum Hamburger Schisma, aus dem die damals so bezeichnete Allgemeine christlich apostolische Mission entstand. Dieses Schisma ist die Geburtsstunde der Neuapostolischen Kirche.

1865 kommt Wilhelm Menkhoff, Pastor der Holländisch-Reformierten Kirche in Oudekerk (bei Amsterdam), nach Bielefeld. Er hatte in Holland die katholisch-apostolische Lehre kennen- und schätzen gelernt. Im Bielefeld trifft er mit Hermann Niehaus zusammen, dessen Eltern in Steinhagen einen kleinen Hof bewirtschaften. Dort führt Wilhelm Menkhoff Gottesdienste durch. 1867 verlegt er seinen Wohnsitz wieder zurück nach Bielefeld und wohnte fortan in seiner Wohnung „Am Sparrenberg 2“. Hier hielt er Gottesdienste, Bibelstunden und Vorträge. Damit verbunden war zugleich die Kündigung in seiner angestammten reformierten Kirche - Wilhelm Menkhoff wurde zu einem glühenden Verfechter der apostolischen Lehre. Die Familie Niehaus und viele andere Christen aus Quelle-Steinhagen machten sich regelmäßig auf den Weg nach Bielefeld, um diesen Mann zu hören. Auch auf dem Niehaus'schen Anwesen in Quelle fanden nun regelmäßig Versammlungen statt.

Dies waren die ersten neuapostolischen Gottesdienste in Nordrhein-Westfalen überhaupt. Das erste richtige Kirchenlokal, das eigens für Gottesdienste zur Verfügung stand, wurde 1869 in Bielefeld eingeweiht. Viele Hundert Seelen sind in den Folgejahren hinzugekommen. Die zunächst kleine Gemeinde wuchs über die Grenzen Bielefelds hinaus in das ganze Land Nordrhein-Westfalen. Wilhelm Menkhoff wurde 1872 zum Apostel ordiniert und wirkte künftig in Westfalen. 1895 verstarb dieser treue Diener seiner Kirche, seine Grabstätte ist heute noch auf dem Gadderbaumer Friedhof zu sehen. Hermann Niehaus wurde sein Nachfolger und von 1905-1932 sogar Stammapostel und damit oberster Leiter der Neuapostolischen Kirche.

1902 zog die Bielefelder Gemeinde in die Große-Kurfürsten-Straße, 1920 in die Dorotheenstraße. Einige weitere Bielefelder Gemeinden konnten gegründet werden. Heute zählt der Bielefelder Kirchenbezirk 12 selbständige Gemeinden, 9 davon auf dem eigentlichen Stadtgebiet Bielefelds.

Brake, Jöllenbeck, Heepen-Kammeratsheide, Mitte (die Muttergemeinde), Ost, Schildesche, Sennestadt, Süd und Ummeln. Außerhalb des Stadtgebiets gibt es ferner Gemeinden in Halle-Werther, Quelle-Steinhagen und Versmold. Sie alle gehören organisatorisch zum Kirchenbezirk Bielefeld.