Als ein Eckpfeiler seines Hochstiftes gegenüber dem mächtigen Kloster Fulda plante der Würzburger Bischof Konrad von Querfurt, während seiner nur vierjährigen Amtszeit von 1198 bis 1202 die Stadt Karlstadt nach den modernsten damaligen Vorbildern neu gegründeter und befestigter Städte in der Lombardei. Kirchlich dürfte die Stadt von Anfang an selbständig gewesen sein. Dafür sprechen die erhaltenen Teile der Stadtpfarrkirche St. Andreas, deren Turm dem frühen 13. Jh., also der unmittelbaren Stadtgründungszeit angehört. Seine Dimensionen lassen eine relativ große dazugehörige Kirche annehmen. Von diesem romanischen Gotteshaus sind noch die Westmauer des Langhauses mit dem romanischen Portal, Teile der Vierungspfeiler mit den darauf ruhenden Scheidbogen, der untere Teil der Langhausmauern, sowie die alte Sakristei, heute Taufkapelle, erhalten. Die alte Sakristei war ein abgeschlossener Raum, dessen Untergeschoß nur von innen durch eine kleine Türe vom Altarraum her und dessen Obergeschoß nur vom Dach des Chores aus erreichbar war. Es war demnach hier in der Ecke zwischen Chor und Langhaus ein Turm angefangen und zwei Geschosse hoch aufgeführt. Zur Vollendung kam er jedoch nicht, da man sich vermutlich noch während des Baues entschloss, den jetzigen Westturm zu errichten.. Die Westmauer des Langhauses ist also älter als der Turm. Der Turm ist mit der früher fertiggestellten Westmauer des Langhauses nicht bündig und unterscheidet sich davon auch im Mauerwerk. Dieses besteht aus Bruchsteinmauerwerk in kleinen Schichten mit ausgestrichenen Fugen, während der Turm mit großen Quadern aufgeführt wurde. Erst vom vierten Geschoß ab geht das Quaderwerk im Verband durch. Im Laufe der Zeit geriet die Baumasse des Turmes jedoch immer mehr in Bewegung, tiefe Risse taten sich auf und drohten den Turm zum Einsturz zu bringen. 1955 wurde der spätromanische Turm abgebrochen, die Steine nummeriert und auf dem Kirchplatz gelagert. Mit einem entsprechende Fundament versehen wurde der neue Kirchturm dann in Stahlbeton gefertigt und die wieder verwendbaren, vorher nummerierten Steine, Säulen und sonstigen Architekturteile wieder an ihrem angestammten Platz eingefügt. Die erste offizielle Nachricht über die Existenz der Pfarrei St. Andreas bildet ein Erlass des Bischofs Otto von Wolfskehl vom 26.August 1339. Der Bischof wendet sich an die Rektoren der Kirchen in den Städten des Bistums, darunter auch in Karlstadt, und beschwert sich, dass verschieden Richter des päpstlichen Stuhles Richtersprüche und Urteile verkündigten, wodurch große Verwirrung entstünde.