Am 12. April 963 gelangte der Moselgaugraf Siegfried durch einen Gebietstausch in den Besitz der über dem Tal der Alzette gelegenen Lucilinburhuc oder Lützelburg (= kleine Burg). Die Burg und die umgebenden Ländereien hatten bis dahin dem Kloster St. Maximin in Trier gehört. Ein solcher Gebietstausch war etwas Alltägliches, und doch haftet ihm etwas Besonderes an, markiert er doch den Beginn der luxemburgischen Geschichte. Graf Siegfried erneuerte die am Kreuzungspunkt wichtiger Verkehrswege gelegene Burg und machte sie zur Keimzelle einer städtischen Siedlung. 1224 erhielt Lützelburg-Luxemburg die Stadtrechte. Bereits im 11. und 12. Jahrhundert hatten die Luxemburger Grafen ihren Besitz an der Mosel und in der Eifel kontinuierlich ausgedehnt.
Dabei half eine äußerst vorteilhafte Verbindung: Im Jahr 1000 heiratete die Luxemburger Grafentochter Kunigunde den Bayernherzog Heinrich IV., der zwei Jahre später als Heinrich II. zum römisch-deutschen König gewählt wurde. Kunigundes Bruder stieg im Windschatten des kaiserlichen Schwagers zum Herzog von Bayern auf. Das Verhältnis zwischen Heinrich II. und seiner Verwandtschaft verlief in der Folge zwar alles andere denn reibungslos (zeitweise entzog der Kaiser seinem Schwager das Herzogtum wieder), doch die Luxemburger hatten damit endgültig den Fuß in die Tür der großen Politik gesetzt.
Eine Zäsur bildete das Jahr 1136, in dem Graf Konrad II. von Luxemburg kinderlos verstarb. Über eine Tante Konrads fiel die Grafschaft an Heinrich von Namur. Er konnte die Stammgrafschaft durch einige Erbfälle im Gebiet von Mosel und Maas beträchtlich erweitern, hatte aber mit weiteren, militärischen Expan-sionsversuchen nur wenig Glück. Wenig Glück hatte Heinrich auch mit seiner Ehe – zuerst schickte er seine Frau Agnes von Geldern nach vier Jahren wegen der ausbleibenden Mitgift wieder nach Hause, um sich, schon über 70 Jahre alt, wieder mit ihr zu versöhnen, vermutlich wegen des fehlenden Erben.
Tatsächlich gebar Agnes 1186 eine Tochter – Ermesinde –, die der Vater im Alter von einem Jahr mit Graf Heinrich II. von der Champagne, einem Neffen des französischen Königs Philipp II. August, verlobte. Doch damit machte der alte Luxemburger das Chaos erst perfekt: Friedrich I. Barbarossa, der selbst ein Auge auf die söhnelose Grafschaft geworfen hatte, fühlte sich dadurch vor den Kopf gestoßen, ebenso die Familien von Heinrichs Schwestern. Der Versuch, die französische Krone in das Spiel um die Macht in Luxemburg einzubeziehen, zeugt zugleich von der langen Tradition der Mittellage Luxemburgs zwischen französischen und deutschen Interessen. Das Rennen um die Grafschaft Luxemburg machte schließlich Graf Theobald von Bar, der 1197 die damals elfjährige Ermesinde geheiratet hatte, nachdem die Verbindung mit dem Grafen Heinrich von der Champagne nicht zustande gekommen war…
