Pierwszy kościół w Kołkach powstał prawdopodobnie w drugiej połowie XV wieku z fundacji ówczesnych właścicieli majątku, rodu von Wedel. Była to budowla murowana z kamienia polnego, salowa, bezwieżowa, usytuowana w zachodniej części wsi. W połowie lat 60. XIX wieku obiekt znajdował się w bardzo złym stanie technicznym i został rozebrany, z wyjątkiem ściany zachodniej, którą zabezpieczono jako trwałą ruinę. W 1931 roku wykorzystano ją do utworzenia pomnika poległych w I wojna światowa.
Nowy kościół wzniesiono w latach 70. XIX wieku w innym miejscu, przy skrzyżowaniu dróg wiejskich. Fundatorami byli przedstawiciele rodu von Schuckmann, do których należało prawo patronatu. Do nowej świątyni przeniesiono dwa starsze dzwony: większy, o średnicy 88 cm, odlany w 1586 roku przez Jakoba Stellmachera i ufundowany przez Hansa i Kaspara von der Osten, oraz mniejszy, o średnicy 79 cm, odlany w 1716 roku przez Johanna Dietricha Schmidta z Drawna i ufundowany przez Hansa Joachima von der Osten.