Eine erste Kirche zu Artlenburg, unmittelbar an der Elbe gelegen, dürfte bereits im 12. Jahrhundert existiert haben. Das 1779 zuletzt erneuerte Kirchenschiff fiel einem Kirchenbrand 1821 zum Opfer. 1825/27 wurde das Gotteshaus in der heutigen Form neu errichtet. Besonders ist hier die gesüdete Lage des Altars.
Der untere Teil des im Kern romanischen Rundturms besteht aus Feldstein, auf welchem sowie die oktogonale Glockenstube aus Fachwerk sitzen. Der Turm besitzt auf seiner gesamten Höhe eine Backsteinummantelung und erfuhr zuletzt 2001 eine Sanierung.
Mit dem Kirchenbrand ging auch das alte Geläut zugrunde, welches aus zwei Glocken der Jahre 1705 und 1727 sowie einer weiteren, wohl mittelalterlichen Glocke bestand. Der Gießer Johann Heinrich Dreier goss zum Wiederaufbau zwei neue Glocken, von denen die große im Ersten Weltkrieg eingeschmolzen wurde. Zwei 1923 als Ersatz in Auftrag gegebene Eisenglocken wurden 1975 vor der Kirche aufgestellt und durch zwei neue Bronzeglocken ersetzt.