Deze driebeukige hallenkerk met achtzijdige westtoren gaat terug op een 13de-14de-eeuws kerkgebouw met schip, kruisbeuk met vieringtoren en koorpartij. Hiervan zijn het noordelijke zijkoor (13de eeuw), het zuidelijke zijkoor en het onderste gedeelte van de toren (14de eeuw) bewaard. Door vernielingen gedurende het laatste kwart van de 16de en eerste kwart van de 17de eeuw werd beslist om het westelijke deel van het schip te slopen, waardoor de vieringtoren nu als geveltoren dienst doet. In 1717 wordt aan de vieringtoren een klein voorportaal gebouwd. De torenspits heeft de Klemskerkenaren heel wat hoofdbrekens bezorgd. Hij brandde in totaal drie keer af als gevolg van blikseminslagen (1696, 1715 en 1770). De Klemskerkenaren wilden na de derde maal de toren niet meer heropbouwen, maar werden hiertoe verplicht door de overheid met als reden dat de torenspits als baken fungeerde voor de zeelieden om zandbanken te vermijden.
De kerk is omgeven door een ommuurd kerkhof omzoomd met hagen en knotwilgen en een omlopende bakstenen stoep. Het geheel is als monument geklasseerd.
Het interieur werd onder leiding van architect Ammery tijdens de periode 1890-1895 grondig gerestaureerd. Uit die tijd stammen de neogotische elementen: het kruistafereel aan het hoofdaltaar, de zijaltaren en de preekstoel. De 17de-eeuwse schilderijen, biechtstoelen, kerkmeesterbanken en polychrome beelden bleven bewaard. Het Van Peteghemorgel dateert van 1832.
In 1902-1903 werd er een buitenrestauratie uitgevoerd waarbij het roosvenster werd aangebracht boven het westelijke portaal.
Bij opgravingen tijdens de laatste restauratiewerken in 2010 werden talrijke artefacten gevonden, waaronder aardewerkscherven en muntstukken daterend van de twaalfde tot de zeventiende eeuw. Ook werden twaalf grafkelders blootgelegd en twee kistbegravingen aangetroffen en zeven menselijke skeletten. Men besliste om de grafkelders niet zichtbaar te maken. De aangetroffen grafstenen in gezoete blauwe hardsteen werden opgehangen in het portaal. Enkele van deze artefacten zijn tentoongesteld in vitrinekastjes achteraan in de kerk.