Miasto powstało przez zrośnięcie się dwóch wsi, Ufhofen i Mittelhofen, miejscowości leżały u podnóża kościoła ludowego pw. św. Marcina (Leutekirche). Miasto wzięło nazwę właśnie od tego kościoła, dzisiaj jest on umieszczony w herbie miasta. Pierwsza autentyczna wzmianka o kościele i sądzie Nibelgau pochodzą z dokumentów opactwa St. Gallen i są datowane na 766, było to po wyginięciu grafów Udalriching i Weitern, gdy tereny te przejęły właściciele Bregencji i grafowie Montfort. Tymczasem między Ufhofen i Mittelhofen powstał targ.
W 1293 dla Leutkirch przez Adolfa z Nassau zostały nadane prawa miasta Lindau (Bodensee), w wyniku czego Leutkirch stało się wolnym miastem Rzeszy.
Głównym rzemiosłem rozwiniętym w mieście było tkactwo (produkcja płótna), największy cech liczył do 200 członków, wyroby były przesyłane do Włoch i Hiszpanii. W 1488 Leutkirch zostało członkiem Ligi Szwabskiej i uzyskało miejsce oraz głos w parlamencie i lidze.
W 1546 miasto dołączyło do reformacji.