Eine steinerne Rundnackenaxt aus Serpetin aus der Jungsteinzeit und eine Münze aus der jüngeren Eisenzeit (eine nordische Tetradrachme) geben Zeugnis von der Ur- und Frühgeschichte Leutschachs. Die Besiedlung in römischer Zeit dieses Gebietes beweisen Grabfunde, die man 1949 heben konnte. Marmorne Löwen, die als Wächter bei diesen Gräbern standen, wurden restauriert und befinden sich im Eingang zum Rathaus.

Die erste urkundliche Nennung des Ortes erscheint im Jahre 1250 in seiner damals üblichen Form "Liubschach", allerdings nicht in Verbindung mit dem heutigen Ort, sonder als Zuname zweier Ritter namens Ulrich und Chrepilo. Diese beiden adeligen Herren waren in der Gegend "Liubschach" ansäßig und stellten sozusagen die ersten "Leutschacher" dar. Die beiden Ritter selbst traten 1250 als Dienstmannen der im selben Jahr erstmals genannten "Smilnburch" auf, jener Burg, deren Ruinen heute noch unter dem Namen Schmirnberg in der Gemeinde Schloßberg zu sehen sind.

Die Gegend um Leutschach hat schon im 13. Jahrhundert und früher zur Burg Schmirnberg gehört. Kaiser Friedrich III. entriss Schmirnberg den Grafen von Cilli und machte es 1445 zur landesfürstlichen Lehens- und Pfandherrschaft. Er hat der Burg 1445 auch die Blutgerichtsbarkeit verliehen und sie so auch zur alleinigen Gerichtsherrschaft ("Landgericht") über ihre Gründe und Untertanen gemacht. 13 Jahre später, 1458, verlieh er dem Ort Leutschach das Markt- und Bürgerrecht.

Durch diese Markterhebung und das Vorrecht, sich Richter und Rat selbst zu wählen und eine eigene Rechtssprechung über Markt und Bürgerschaft auszuüben, ist Leutschach 1458 auch aus der unmittelbaren Verwaltung und Gerichtsbarkeit Schmirnbergs ausgeschieden. Als Zeichen dieser Selbstverwaltung und Eigengerichtsbarkeit ist für Leutschach zum ersten Mal 1480 "der Richter" und das von ihm gehandhabte "Gericht" genannt. Dieser annähernd mit dem heutigen Bereich der modernen Gemeinde Leutschach identischen Gerichtssprengel hieß damals "Burgfried" unter welcher Bezeichnung er für Leutschach 1505 erstmals auftritt.

Zugleich mit ihm ist auch der erste bekannte Marktrichter Leutschachs, der "erbar und weise" Herr Primus, genannt. Als die Soldaten Sultan Solimans II. 1532 aus Ungarn hier in die Steiermark einbrachen, eroberten sie Leutschach nachweislich und brannten es nieder. Der Ort wurde zwar wieder aufgebaut, aber 1547 und 1559 durch Feuerbrünste abermals zerstört. Der Wiederaufbau des Marktes seit der Mitte des 16. Jahrhunderts schuf daher einen eigenen ganz neuen Baubestand und ließ damit jene neuzeitliche Siedlung entstehen, deren Ortsform noch im Ortsplan Leutschachs von 1820/25 deutlich zu erkennen ist.

Leutschach stellt schon im 16. Jahrhundert einen Straßenknotenpunkt dar (Ehrenhausen - St. Georgen a.d.P. - Schmirnberg - Arnfels). Bereits im 17. Jahrhundert bestand in Leutschach ein Altersheim für arbeitsunfähige oder kranke Bürger. Es scheint 1667 als das sogenannte Heiligengeist-Spital auf. Kaiser Ferdinand II. verlieh dem Markte Leutschach zugleich das Jahrmarktprivileg und das Recht zur Führung eines Siegelbildes. Die Verleihung eines farbprächtigen Marktwappens durch den Kaiser fand im Jahre 1625 statt. Bis zum 1.1.1883 standen die Gemeinden Leutschach, Glanz, Eichberg-Trautenburg und Schloßberg unter einem Bürgermeister. Die genannten Gemeinden trennten sich ab diesem Zeitpunkt von Leutschach und wurden selbständig.