1401 wird erstmals eine Kirche St. Nikolaus erwähnt, es existierte aber schon seit dem 11. Jahrhundert eine Kirche an dieser Stelle. 1555 wurde in der Gemeinde die Reformation eingeführt und die Kirche in eine lutherische umgewandelt. Während des 18. Jahrhunderts, als die Wild- und Rheingrafen ihre Residenz nach Gaugrehweiler verlegten, nutzten sie die Dorfkirche auch als Hofkirche, einige Mitglieder ihrer Familie wurden dort bestattet. Bis in die 1970er Jahre hinein war die Kirche in Gaugrehweiler eine eigenständige Pfarrkirche, dann wurde die Verwaltungsstruktur geändert und die Pfarrei aufgelöst. Gaugrehweiler wurde zur Filialkirche von St. Alban.

Der romanische Baukern der Kirche stammt aus dem 11. Jahrhundert. In gotischer Zeit wurde ein Seitenschiff hinzugesetzt. Eine umfassende Renovierung und Veränderung wurde von den Wild- und Rheingrafen in der zweiten Hälfte des 18. Jahrhunderts durchgeführt. Die Kirche barock überformt und steht seitdem als Putzbau dar. Im Dachaufbau befindet sich noch das 1754 installierte Uhrwerk, es wurde 1872 erneuert. Von der barocken Innenausstattung ist nur der reich profilierte Kanzelkorb erhalten. In den Chorfenstern sind noch die Wappenscheiben zweier Rheingrafen zu sehen. Unter dem Altarraum befindet sich die Familiengruft.