Die Kirche gilt als das älteste Gebäude in Bad Friedrichshall-Kochendorf und ist gemäß architektonischer Befunde vermutlich vor 1100 entstanden. Die ursprünglich ummauerte Wehrkirche wurde 1294 beim Verkauf des Patronatsrechts an das Stift Wimpfen erstmals erwähnt. Die Kirche unterhalb des Greckenschlosses war Grablege des Kochendorfer Ortsadels. Kochendorf wurde 1549 durch Wolf Conrad I. Greck reformiert. Der Ortsherr war vermutlich durch seine Ehe mit Sibylla von Gemmingen reformatorisch beeinflusst. Das Patronatsrecht verblieb auch nach der Reformation beim katholischen Stift Wimpfen, das 1595 einen Kirchenneubau durchführte. Um die Kirche befand sich vor dem Neubau auch der Friedhof, mit dem Neubau hat man einen neuen Friedhof südwestlich des Ortes angelegt. Der 1655 nach Blitzschlag beschädigte Kirchturm wurde 1661 instand gesetzt. Als im napoleonischen Zeitalter Klöster und reichsritterschaftliche sowie reichsfreie Gebiete aufgehoben wurden, kam Kochendorf zu Württemberg, Wimpfen dagegen zu Hessen. Dadurch gelangte das Patronatsrecht nach 1802 an die Landgrafen von Hessen-Darmstadt. Erst im Jahr 1906 kam die Gemeinde in Kochendorf schließlich zur evangelischen Landeskirche von Württemberg. 1871/72 wurde die Kirche umfangreich renoviert. Einige historische Grabmale wurden an die Außenwand versetzt, und anstelle älterer Außentreppen zu den Emporen wurden zwei Treppentürme angebaut. Zur Ausstattung der Kirche zählten der Taufstein und der Altar, beide 1859 von Zartmann in Neckarsulm geschaffen, eine kleine alte Orgel mit Evangelistendarstellungen, die 1861 restauriert worden war, eine zweistöckige Empore im Westen mit Aposteldarstellungen sowie die Orgelempore im Osten mit einer 1878 bei Schäfer in Heilbronn gebauten neuen Orgel mit 18 Registern. Die drei Glocken waren 1765 bei Mezger in Heilbronn gegossen worden. Im Chor befanden sich mehrere Grabdenkmale, darunter das doppelte Steindenkmal für Wolff Greck von Kochendorf († 1533) und seine Frau Kunigund von Liebenstein († 1534) mit bemalten lebensgroßen Relieffiguren sowie das rund fünf Meter hohe Grabdenkmal für Wolf Konrad Greck († 1598) und seine beiden Frauen Sibylle von Gemmingen († 1567) und Amalie Altdorf gen. Wolfschlag († 1588). Zu den weiteren Grabmalen zählten das des Joachim Heinrich von Ellrichshausen († 1674) sowie die hölzernen Epitaphe für Wolf Konrad Greck mit Familie sowie den Arzt Georg Andreas Schiebel († 1799). Im April 1945 wurde die Kirche bei Kampfhandlungen von den heranrückenden amerikanischen Truppen in Brand geschossen. Trotz erster Löschmaßnahmen blieben vor allem in der Torfisolierung des Daches Glutnester zurück, die wegen der fortdauernden Kämpfe nicht mehr gelöscht werden konnten, so dass die Kirche schließlich bis auf die Grundmauern niederbrannte. Alle Ausstattungsgegenstände, darunter auch die historischen Grabmale, wurden zerstört. Lediglich im Chorbereich blieben einige wenige historische Relikte erhalten, darunter ein gotisches Sakramentshaus sowie Reste von Wandmalereien. Die Sebastianskirche wurde bis 1948 restauriert und erhielt 1952 neue Glocken aus der Glockengießerei Bachert. Über dem Portal des Seiteneinganges steht auf einer Sandsteinplatte das Psalmwort Herr, ich habe lieb die Stätte deines Hauses und den Ort, da deine Ehre wohnt (Psalm 26,8). Über dem Eingang befinden sich die Stammwappen derer Greck von Kochendorf und von Gemmingen. Die 1765 bei Metzger in Heilbronn gegossenen Glocken der Sebastianskirche wurden während des Zweiten Weltkrieges im März 1942 zu Waffen umgegossen. Nach dem Krieg wurden von der ortsansässigen Glockengießerei Bachert fünf neue Glocken gefertigt, welche 1952 in den Kirchturm kamen. An den Außen- und Innenwänden der Sebastianskirche befanden sich zahlreiche Epitaphe. Einige davon wurden bei Kampfhandlungen im April 1945 zerstört, andere sind heute noch erhalten. Darunter sind Grabmale derer Greck von Kochendorf, von Gemmingen, Kolb von Wartenberg und von Berlichingen.
