Das Bauerndorf Sehma gehörte kirchlich zu Schlettau. Die Entwicklung nach Jahrhunderten führte aber dahin, daß es ein selbständiges Kirchspiel werden wollte. Um dies zu erreichen, war ein schwerer Kampf mit der Mutterkirche Schlettau zu führen. Nach vielen, fast 10 Jahren war die Selbständigkeit erkämpft. Bereits 1666, als Hoffnung bestand, wurde die erste Kirche erbaut, durfte aber noch nicht benutzt werden. Erst 1673 konnte sie geweiht werden.

Nun wurde aber auch ein Pfarrgut gebraucht mit Wohnung für den Pfarrer. Dazu ergab sich die Gelegenheit zum Kauf des Gutes OL_26. Dieses stand gegenüber der neuen Schule, welche 1887 erbaut wurde.

Das zum Pfarrhaus umgebaute Gut war also etwas südlicher als die neue Kirche, war auch trotz des Umbaues unpraktisch geblieben.

Die Kirchgemeinde befaßte sich damals mit dem Bau einer neuen Kirche und neuem Pfarrhaus. Nach 10 Jahren war es soweit. 1897 war ein neues Pfarrhaus bezugsfertig und anschließend wurde die neue Kirche gebaut. Die neue „Pauluskirche“ konnte 1899 geweiht werden und vorher konnte der neue Pfarrer Max Führer das Pfarramt als sein Heim beziehen.

Über den Bau der Pauluskirche ist eine besondere Ausfertigung zusammengestellt und dem Ordner „Ortsgeschichtliches“ eingeheftet worden.