Die Geschichte der Kleinstadt ist eng mit Altmarkt - Stari trg verknüpft, denn dort entstand während der classischen Periode eine römische Siedlung namens Colatio. Das mittelalterliche Schloss über Stari trg wurde zuerst in 1091 als Grez ('Gradec') aufgezeichnet, somit ist das nach Aufzeichnungen das zweit früheste Schloss in der Steiermark und im Kärnten von Slowenien. Der Name wurde auf die in der Nähe liegenden Siedlung, die einen günstigeren Standort auf einer 10 m höhen Sandbank Terasse zwischen den Flüssen Suhodolnica und Mislinja fand, übertragen. Die Siedlung direkt unter dem Schloss wurde aber als Stari trg (Altmarkt) bekannt. Slovenj Gradec wurde von den Grafen von Andechs gegründet, die die Herrschaft über die Kleinstadt am Ende des 12. Jahrhunderts übernahmen, dennoch blieb dieses Gebiet eine separate Einheit zwischen beiden Provinzen Kärnten und Steiermark bis zum 15. Jahrhundert. Es was als Altmarkt erst im Jahr 1251 aufgezeichnet, als Berthold von Andechs, der Patriarch von Aquileia, seine ganze Besitzung dem Gebiet von Slovenj Gradec donierte: das Schloss mit der Kirche, den Stadtteil und und andere Plätze wie Ministerialen, Mauthaus und Minze, bis zum Patriarchat von Aquileia (das heutige Italien).
Wegen der großen Entfernung zwischen Slovenj Gradec und Aquileia beteiligten sich die nahe gelegenen Feudalherren an dem Kampf um die Herrschaft von Slovenj Gradec. Die Behörde über wurde vom Herzog Ulrich III, Spanheim von Kärnten, angenommen und er gewährte zivilrechtliche Taten in Slovenj Gradec in 1267. Anschließend war die Stadt für einige Zeit im Besitz von Otokar II, dem König von Böhmen, bevor die Patriarchen von Aquileia ihre Autorität wieder aufnahmen.
Die Familie von Windischgrätz, die aus Oberbayern als Minister für die Grafen von Andechs ankamen, war eine der interessanten Familien, die in Slovenj Gradec ihren Wohnsitz hatten. Anschließend wurden sie zu einer der prominentesten Familien im Habsburgerreich.
Aufgrund seiner günstigen geographischen Lage und Transitrouten, begann die Kleinstadt Slovenj Grade zu florieren. Allerlei Handwerk und Handel entwickelten sich, Stadtmauer wurde gebaut, und die Stadt erhielt Messe-Rechte und Judikatur sowie eine Minze.
Die Habsburger trugen zur Entwicklung der Stadt bei, nachdem sie das Dominion von Slovenj Gradec in der zweiten Hälfte des 14. Jahrhunderts übernommen hatten und übergaben es zu verschiedenen Feudalherren der Steiermark, so wurde die Besitzung im Jahr 1407 zu einem Teil der Provinz Steiermark.
Die Judikatur der Stadt wurde erweitert, die Entwicklung von Handwerk und Handel in ihrer Umgebung geregelt und es wurde in der Stadt ein bedeutendes Lagerhaus für Salz aus der Region Salzburg gebaut. Die Salzgrenze lief der Slovenj Gradec Gegend entlang: Salz aus Aussee in der Steiermark wurde ausschließlich im Norden der Salzgrenze verkauft, während Meersalz im Süden verkauft wurde.
Neue Reisemöglichkeiten entstanden für die Bewohner von Slovenj Gradec mit einer neuen Einstellung zum Wissen, das im späten Mittelalter hervorgerufen wurde. Piligrin, der Pfarrer von Slovenj Gradec, studierte in Bologna, Italien, schon im 14. Jahrhundert, während Nicholaus von Slovenj Gradec an der Universität Wien in der zweiten Hälfte des 15. Jahrhunderts lehrte, um der erste Kanzler aus dem heutigen Territorium von Slowenien im Jahre 1437 zu werden. In den 1470-er, als sogar vier Studenten aus Slovenj Gradec an der Universität Wien studierten, war unter ihnen auch Matthaeus Cerdonis de Windischgretz (etwa 1445-1487 oder danach), der letzte unabhängige Drucker der Inkunabeln in Padua, Italien. Über 60 seiner Drucke wurden bisher aus den Bereichen Medizin, Mathematik, Astronomie, sowie Recht und Geisteswissenschaften anerkannt.
Im späten Mittelalter war Slovenj Gradec auch ein wünschenswertes Ziel, das Menschen anzog; einige kamen als Siedler an (z. B. der wohlhabende Bürger Johannes von Lakh, der das Stadthaus errichtete), andere als Künstler (Andreas von Otting, der Maler der Fresken in der Kirche des Heiligen Geistes), viele von ihnen als Reisende (Hugo Grotius) oder Besucher (Maximilian I., König des Heiligen Römischen Reiches, der ein paar Tage in Slovenj Gradec im Jahre 1514 verbrachte).
Während des 15. und 16. Jahrhunderts war Slovenj Gradec nicht von den Ereignissen befreit, die die Geschichte von Kontinentaleuropa prägten: das Land wurde von den Türken und das Tal 1477 von Heuschrecken verwüstet, die Stadt wurde in 1489 von den Soldaten von Matthias Corvinus besetzt, dem König von Ungarn, und später intensiv von der ersten Welle der Reformation im Jahre 1525 ergriffen. Der neue Glaube wurde von den meisten Bürgern und Aristokraten aus der Umgebung angenommen. Die Bewegung wurde schließlich von einer Gegenreformationskommission unterdrückt, die alle lutherischen Bücher verbrannte und die kleine Kirche und den Kirchhof schon 1600 herunterzog (und der katholische Glaube wurde wieder aufgenommen).
Dennoch, der Name der Stadt - Slovenj Gradec - das war zuerst in seiner slowenischen Form von Primož Trubar geschrieben (ein führender Protestant und der Gründervater der slowenischen Sprache) und ist als ein bleibendes Erbe des Protestantismus geblieben.
In den folgenden Jahrhunderten wurde die Stadt restauriert. Neben dem Handel und den verschiedenen Handwerken entwickelten sich auch die Künste, so wurde Slovenj Gradec ein bedeutendes Zentrum der Kunst und Handwerk im 17. und 18. Jahrhundert. Zahlreiche Handwerker - vor allem Gulden und Graveure - bedienten die Bedürfnisse der Bürger, während Maler und Bildhauer Kirchen umgestalteten. Verschiedene Meister hatten damals ihre Werkstätten in der Stadt: Michael Scobl, Franz Michael Strauss - sein Sohn Johannes Andreas Strauss sowie der Bildhauer und Laubwerker Johann Georg Mersi. Das kultivierte Erscheinungsbild der Stadt wurde zusätzlich von Künstlern aus anderen Teilen des Landes verstärkt (z. B. Johann Jacob Schoy). Es ist erwähnenswert, dass die Meister der barocken Werkstätten aus Slovenj Gradec die Kirchen an zahlreichen Orten im slowenischen Teil der Steiermark verziert haben.
Im 19. Jahrhundert entwickelte sich Slovenj Gradec zu einer Stadt im modernen Weltgeist. Die Häuser im Zentrum erwarben ein moderneres und prächtiges Aussehen nach bürgerlichem Geschmack; einige von ihnen sind bis zum heutigen Tag trotz des Brandes im Jahre 1903 erhalten geblieben. Die Stadt war der Sitz des Bezirksgouverneurs und Judikatur, Messungsbüros, Gendarmerie, Schule, Armenhauses, Krankenhauses, von zwei Hotels und mehreren Gasthöfen. Ein neues Krankenhaus wurde im Jahre 1898 gebaut und die elektrische Beleuchtung, die von einer eigenen Anlage angetrieben wurde, wurde 1903 eingeführt. Der erste Zug erreichte die Stadt 1899, vier Autos und acht Motorrädern folgten nur ein Jahrzehnt später.