Um das Jahr 1000 verfügte die Gräfin Wichburg in der Umgebung von Bleiburg/Pliberk über einen großen Besitz. Im Jahre 1020 gründete sie das Kloster St. Georgen am Längsee und stiftete diesem 15 Bauernhöfe in „Ljupikdorf“ bei Bleiburg/Pliberk. Der Name „Ljupikdorf“ ist slawischen Ursprungs. „Ljub“ bedeutet im Deutschen „lieb“. Auch der westlich von Bleiburg gelegene Hügel heißt „Libitsch/Libič“ und das Dorf „Loibach/Libuče“. Also stand „Ljupikdorf/Ljubičja vas“ unter der Burg „Plyburch“ und vielleicht sogar auf dem Boden, auf dem heute die Stadt Bleiburg/Pliberk steht.
Diese Ländereien gehörten den bajuwarisch-palatinischen Grafen Aribon, von denen einer — nämlich Albuin — Bischof von Brixen war. Albuin schenkte Aribon die Grafschaft bei „Luikpikdorf“, wahrscheinlich in der Nähe des heutigen Loibach/Libuče. Diesen Besitz erbten später die Heunburger Grafen/Vovbrški grofje Heunburger, welche auch südlich der Drau/Drava Ländereien besaßen. Graf Albero war schon 1195 Eigentümer von „Mineburg«, einer Burg, welche auf dem heutigen Reš-Besitz in Moos/Blato stand. Diese Burg wurde also schon vor dem Schloss in Bleiburg errichtet. Weil sie jedoch wahrscheinlich ein Holzbau war, blieben von ihr nur die Schutzgräben erhalten. Schon im 13. Jh. wurde beurkundet, dass nur noch Ruinen von ihrer Existenz zeugen. Die Heunburger Grafen gründeten schließlich den Markt Bleiburg/Pliberk und erbauten hier eine Burg.
In Urkunden begegnet uns der Name „Plyburch“ erstmals am 9. Mai 1228. Sicher stand aber sowohl die Burg als auch der Markt schon vorher, hatte doch Graf Wilhelm IV. von Heunburg den Markt (Forum) Plyburch und die Burg seinem Schwager, dem Ortenburger Hermann II., verpfändet. In dieser Zeit wird auch der Marktrichter erwähnt und davon berichtet, dass ein Sohn des Heunburger Grafen Pfarrer in der Urpfarre in St. Michael ob Bleiburg/Šmihel nad Pliberkom war.
Der Heunburger Graf Ulrich III. heiratete die fürstliche Babenberger Witwe Agnes und verlegte seinen Sitz nach Plyburch, um so näher bei den Besitztümern seiner Frau in der Untersteiermark/Spodnja Štajerska zu sein. Er beabsichtigte, dort ein eigenes Fürstentum zu errichten, was ihm jedoch Rudolf von Habsburg verbot. Dieser zwang ihn auch 1279 in Judenburg, vertraglich darauf zu verzichten und die Erbländer seiner Frau zu verkaufen. Später vertrieben ihn die Habsburger nach Wiener Neustadt, wo die einst mächtigen Haimburger Grafen im Jahre 1322 ausstarben.
Einen Teil der Haimburger Besitzungen, unter ihnen das Schloss Bleiburg, erbten die Grafen Pfannberg. Beide Besitztümer überließen sie als Pfand dem mächtigen Konrad von Auffenstein, welcher Güter schon in Gutenstein, Mieß, Eisenkappel, am Weißensee und noch anderswo besaß. Er erneuerte das Schloss und ließ im Markt eine Kirche erbauen. Später wurde er sogar Marschall von Kärnten. Als aber diese Ehre durch den Habsburger Albrecht einem anderen erwiesen wurde, lehnte sich der Bleiburger Graf dagegen auf. Deshalb belagerten die Habsburger zwei Monate lang das Schloss Bleiburg, die Stadt aber brannten sie 1368 nieder. Schließlich nahmen sie den Grafen und seinen Bruder gefangen, warfen sie in die Kerker von Schloss Strechau, die ihr Urgroßvater für Verbrecher hatte errichten lassen. Dort starb Konrad im Jahre 1396, sein Bruder Friedrich wurde nach 28 Jahren Kerkerhaft begnadigt. Er musste sich jedoch von allen Besitzungen lossagen und wurde Priester. Als Kanonikus von Regensburg starb er schließlich.
Die Habsburger verliehen den Bleiburgern am 15. November 1370 das Stadtrecht, die bürgerlichen und rechtlichen Freiheiten. So wurde Bleiburg die vierte Herzogstadt in Kärnten. Die Bürger brauchten keine Abgaben zu entrichten, erhielten ihren Stadtrichter und ihren Geschworenenausschuss. Ab dem Jahre 1393 durften sie ihren Richter auch selbst wählen. Er durfte innerhalb der Stadtmauern Recht sprechen. Das Aussprechen der Todesstrafe aber behielt sich der Landesfürst selbst vor.