Eine Kirche ist in Kempten schon für das 8. Jahrhundert bezeugt. Als nämlich der hl. Bonifatius den bischöflichen Stuhl zu Mainz bestieg, zog sich sein wegen Untauglichkeit abgesetzter Vorgänger nach Sponsheim zurück. In dieser Zeit wurdem ihm Einkünfte der Kirche zu Kempten überlassen. Nimmt man einen ehedem am mittelalterlichen Kirchturm eingemauerten alten christlichen Grabstein sowie die in der Nähe gefunden fränkischen Grabsteine zu Hilfe, so kann die Kirche nach Meinung Brilmayers, noch wesentlich älter sein. Kempten wäre demnach eine der ältesten Landgemeinden, in denen eine Kirche nachgewiesen ist.
Spätestens im 13. Jahrhundert war Kempten Pfarrei. Die Pfarrkirche war den drei Heiligen Königen geweiht. Das Patronatsrecht stand in früher Zeit dem Domkapitel zu Mainz zu, welches dieses Besetzungsrecht im Jahr 1255 dem Bleidenstadter Abt Hartung abtrat.
Die mittelalterliche Kirche stammte aus dem 13. Jahrhundert. Sie wurde 1690 durch die Franzosen zerstört, dann aber wiederhergestellt. Sie war zusammen mit dem umliegenden Friedhof befestigt.
Im Jahr 1936 wurde die Kirche am Osthang des Rochusbergs erneuert. Die alte, einschiffige Kirche mit gerade geschlossenem Chor wurde als Querbau in den Neubau einbezogen. An der Südseite der heutigen Kirche ist noch ein romanischer Turm erhalten. In der Kirche befindet sich der Grabstein der Bertichildis aus dem 6./7. Jahrhundert, ein Sakramentshaus aus dem 15. Jahrhundert und ein Hl. Johann Nepomuk sowie ein Hl. Valentin von Anfang des 18. Jahrhunderts.