An der Stelle der heutigen Kirche stand laut einer Urkunde des Jahres 823 eine dem hl. Nazarius gewidmete Kirche, die dem Kloster Lorsch übertragen wurde. Diese Kirche, die ursprünglich Filial von Grüningen war, wurde wohl spätestens im 13. Jahrhundert durch eine Kirche ersetzt, die nun den Heiligen Barbara, Katharina und Maternus geweiht war, 1309 selbstständige Pfarrkirche wurde und 1380 dem Patronatsrecht von Kloster Arnsburg unterstellt wurde. Nachdem die Kirche 1566 ihren ersten evangelischen Geistlichen erhalten hatte, der vom katholischen Abt des Klosters Arnsburg präsentiert wurde, führte 1582 Graf Konrad zu Solms-Braunfels das evangelisch-reformierte Bekenntnis ein. 1631/32 wurde dann unter Landgraf Philipp III. von Hessen-Butzbach, der als Lutheraner von 1623 bis 1648 vorübergehend Landesherr in Holzheim war, ein Neubau anstelle der seit 1597 als baufällig bezeichneten alten Kirche errichtet. Unter Einbeziehung des Unterbaus des mittelalterlichen Westturms entstand damals die heute noch bestehende Kirche. Sie ist ein wohlproportionierter Saalbau mit 3/8-Chorschluss, leicht spitzbogigen, großformatigen Fenstern, einem steilen, gaubenbesetzten Satteldach und einem zweigeschossigen Turm, der von einem achtseitigen, dreistufigen Haubenhelm bekrönt wird. Über dem ebenfalls spitzbogigen Nordportal ist das Wappen des Landgrafen und die folgende Inschrift eingelassen: „V. T. D. M. D/ PHILIPPVS D.G. LANDG. HASSIAE/ COMES CATTIMELIB. DECIAE/ ZIGENH. ET NIDDAE ETC: A: C:/ 1631". Charakteristische Details der wohlerhaltenen, reichen Innenausstattung sind die noch aus der Erbauungszeit stammende Flachdecke mit Längsunterzug, geometrischen Stuckaturen und bemalten Medaillons mit biblischen und allegorischen Darstellungen, die von Christoffel Happel aus Grünberg und Andreas Scherer aus Kleinrechtenbach ausgeführt wurden, und die gemalten Fenstereinfassungen. Weiterhin bemerkenswert sind die von toskanischen Säulen getragenen, teils mit Blatt- und Fruchtgehängen bemalten Emporen, von denen die Südempore erst 1852 errichtet wurde, die 1852 hinter den Altar versetzte Kanzel von 1632 sowie die 1830 von H. Berhard aus Romrod geschaffene Orgel.

Einschließlich der im Norden, Osten und Süden teilweise erhaltenen Kirchhofmauer ist die Kirche aus geschichtlichen, künstlerischen und städtebaulichen Gründen Kulturdenkmal. Mit zum Bestand gehört die nach Osten gerichtete romanische Pforte, die die frühe Entstehungszeit der Anlage dokumentiert, das außen in die Nordmauer integrierte Ehrenmal für die Gefallenen des Ersten Weltkrieges sowie die neun aus der Zeit von 1670 bis 1786 stammenden Grabsteine, die auf der Westseite der Kirche aufgestellt sind.