Moderne historikarar reknar at opphavet til Luxembourg kjem frå ordet Letze, som tyder festningsverk[3] og som kan ha vist til anten restane av eit romersk vakttårn eller til ein primitiv tilfluktsstad tidleg i mellomalderen.
Grevskap (963–1353)
Med delinga av Lotharingien i 959 gjekk området til hertug Fredrik I av Øvre Lorraine frå Ardennes-Verdun-dynastiet, ein son av pfalzgreven Wigeric av Lotharingien. I 963 kjøpte grev Siegfried, truleg ein yngre bror av hertug Fredrik I, noko land frå abbed Wikerus av Saint Maximin-klosteret i Trier. Dette landområdet låg krign ruinane av ei ei, visstnok romersk, festning med det gammalhøgtyske namnet Lucilinburhuc (som omfte er omsett til «vesle borg»). Etter få år hadde grev Siegfried bygd ei ny borg over desse ruinane, på ei klippe som seinare vart kalla Bock Fiels. Denne borga dominerte eit område langs den gamle romarvegen mellom Reims, Arlon og Trier, noko som òg opna for handel og toll. Trass i den nybygde borga, ser det ikkje ut til at dette var hovudresidensen til Siegfried og etterkomarane hans. Den verkelege historia til Luxembourg byrjar med bygginga av denne borga.
Dei neste åra voks det fram ein liten by og ein marknad kring den nye borga. Dei første innbyggjarane var truleg tenarane til grev Siegfried og prestestanden frå Saint Michael-kyrkja. Det vart bygd bymur og ei vollgrav kring del ar av busetnaden.
I tillegg til den vesle byen nær Bock Fiels og romarvegen, oppstod det ein annan busetnad i Alzettedalen (i dag Grund-kvarteret). I 1083 hadde denne byen to kyrkjer og to bruer over elvane Alzette og Petruss. Innbyggjarane hadde forskjellige yrke som fiskarar, bakarar og møllarar. Same året vart det grunnlagd eit benediktinarkloster, Altmünster, av grev Konrad på åsen bak Luxembourg slott.
Henrik III var den første kjende greven som budde fast i Luxembourg slott. I eit dokument frå 1089 vert han omtalt som comes Henricus de Lutzeleburg, som òg gjer han til den første dokumenterte greven av Luxembourg.
Kring denne festninga utvikla byen seg gradvis og vart senteret i ein liten, men viktig stat av stor strategisk verdi for Frankrike, Tyskland og Nederlanda. Festninga i Luxembourg vart gradvis utbygd og forsterka over åra av etterkomarane, som gjorde ho til ein av dei mektigaste festningane i Europa. Det formidable festningsverket og den strategiske plasseringa gjorde at ho vart kjend som «Nordens Gibraltar».
Fleire medlemmar av Huset Luxembourg vart tysk-romerske keisarar, kongar av Båohmen, og erkebiskopar av Trier og Mainz. Frå tidleg i mellomalderen til renessansen hadde Luxembourg fleire forskjellige namn, avhengig av forfattarane. Desse var mellom andre Lucilinburhuc, Lutzburg, Lützelburg, Luccelemburc og Lichtburg.
Ermesinde et l'affranchissement de la ville de Luxembourg; Etudes sur la femme, le pouvoir et la ville au XIIIe siècle, sous la direction de Michel Margue, Publications du Musée d'Histoire de la Ville de Luxembourg, Publications du CLUDEM tome 7, Luxembourg 1994.
Tatsachen aus der Geschichte des Luxemburger Landes, Dr. s. J. Müller, Luxemburg 1963, Verlag "de Frendeskres", Imprimerie Bourg-Bourger.
Vivre au Moyen Age: Luxembourg, Metz et Trèves; Etudes sur l'histoire et l'archéologie urbaines, sous la direction du Musée d'Histoire de la Ville de Luxembourg, Publications Scientifiques du Musée d'Histoire de la Ville de Luxembourg, tome 2, Luxembourg 1998.