Die Kirche ist die Nachfolgerin eines ursprünglich in Mentzweiler stehenden Baus, einem Nachbardorf von Cölln. Sie wird erstmals 1353 in den Veldenzer Regesten erwähnt und einige Jahre später 1366 auch im Stolzenburger Burgfrieden. 1544 wurde das lutherische, 1576 das calvinistische Bekenntnis in Cölln und Mentzweiler eingeführt. Im Jahr 1627, während des Dreißigjährigen Krieges, wurde Mentzweiler von spanischen Truppen zerstört und wurde zur Wüstung. Die Kirche hatte den Überfall überstanden und wurde bald vom benachbarten Cölln verwendet. Nachdem der vorherige Bau aufgegeben wurde, baute man an der heutigen Stelle eine neue Kirche, welche inzwischen eine eine Filiale von Oberndorf ist.

Das aktuelle Gebäude entstand 1860/61 nach den Plänen eines Alsenzer Bezirksbauschaffners, ein rechteckiger Saalbau mit Rundbogenfenstern. Auch die Innenausstattung aus dieser Zeit ist noch erhalten. In der Nordwand über der Empore ist eine Steintafel eingelassen, die aus dem Vorgängerbau stammt. Die Inschrift besagt: ANNO 1582 HABEN/ GEMEINE HERSCAFT STOLTZ/ENBERG DIESE KIRCH LAS/SEN BAVVEN MENTZWEILLER/ IM APRIL. Auch die Kirchglocke stammt noch aus dem Vorgängerbau und wird auf das Jahr 1750 zurückdatiert.