Die mittelalterliche Kirche Utzenstorf befand sich in der Herrschaft Landshut (Utzenstorf). Die Kollatur besass wie im benachbarten Kirchberg die Abtei Selz im Elsass. Selz hatte vormals, offenbar lange vor 1481, die Hälfte der Oberherrschaft über die Kirche Utzenstorf dem Schlossherrn von Landshut verkauft. Die Besetzung der Pfrund, das heisst die Wahl des Pfarrers, oblag danach dem Schlossherrn von Landshut (Lerch 1955, S. 20–22). Gleichzeitig mit derjenigen von Kirchberg verkaufte Selz die Kollatur im Jahre 1481 an Bern. Die Herrschaft selbst ging von Thüring von Ringoltingen an dessen Schwiegersohn Ludwig II. von Diesbach, den Besitzer von Schloss Landshut, über. Jener verkaufte die Herrschaft zwei Mal, 1510 und 1514, an Bern. Von 1514–1798 bildete diese Herrschaft, welche die Kirchgemeinden Landshut und Bätterkinden umfasste, die bernische Landvogtei Landshut. Bern besass somit seit 1514 alle Rechte in Utzenstorf.
Die im 11. oder 12. Jahrhundert erbaute, 1275 erstmals erwähnte Kirche von Utzenstorf war ehemals dem Heiligen Martin geweiht. 1457 erhielt sie einen neuen Turm und 1522 erfolgten ein vereinheitlichender spätgotischer Umbau des im Kern romanischen, mehrfach erweiterten Schiffs und der Neubau des Chores. Im Jahr 1925 wurde der Turm erhöht und 1932 der ganze Bau einer Gesamtrenovation unterzogen. Die spätgotische Saalkirche mit dreiseitig geschlossenem, eingezogenem Chor unter fortlaufendem Satteldach erfuhr 1988/89 eine Innen- und 1996–1998 eine Aussenrestaurierung.