Tänapäeva ajaloolased usuvad, et nime Luxembourg etümoloogia on tuletis sõnast Letze (tähendab kindlustust), mis võis tulla kas Rooma vahitorni jäänustest või lihtsast varakeskaegsest varjupaigast. Esimene teadaolev viide territooriumile oli Julius Caesarilt teoses "Commentarii de Bello Gallico", nime tõlgitakse tavaliselt ladina keelest kui "väike loss". Varakeskajastrenessansini kasutasid kirjamehed erinevaid Luksemburgi nimesid, nagu Lucilinburhuc, Lutzburg, Lützelburg, Luccelemburc, Lichtburg.
Krahvkond
Varemetes, oletatavasti Rooma kindlustust Lucilinburhuci on esmamainitud aastal 963, kui krahv Siegfried omandas selle TrieriPüha Maximini kloostriabtilt Wikerilt. Siegfried ilmus esmakordselt 950. aasta paiku, arvatavasti oli ta Lotringi hertsogi Giselberti poeg, tema ema Kunigunde oli Lääne-Frangi kuninga Louis II Kogeleja lapselaps. Järgnevatel aastatel ehitas Siegfried varemete kohale uue lossi, kaljule "Bockfiels". Loss domineeris vana Rooma tee lõigul, mis ühendas Reimsi, Arlonit ja Trieri, mis pakkus väljavaateid kaubandusele ja maksukogumisele. Kuigi Luksemburgi ajalugu algas lossi ehitamisega, näib, et Siegfried ja tema vahetud järglased ei teinud lossi oma esmaseks residentsiks.
Järgnevate aastate jooksul kasvas ümber uue lossi väike linn ja turg. Selle esimesed asukad olid tõenäoliselt krahv Siegfriedi teenrid ja Püha Miikaeli kiriku vaimulikud. Asustus sai varsti lisakaitset, kui ehitati esimene ja osaline linnamüür ja vallikraav. Lisaks väikesele linnale Bockfiels'i ja Rooma tee lähedal asus veelgi elanikke Alzette'i orgu, tänapäeval Luksemburgi Grundi veerand.
Aastaks 1060 laiendasid kindlust Siegfriedi järglased. Konrad I (suri aastal 1086) oli esimene, kes kutsus end "Luksemburgi krahviks". Tema poeg Heinrich III oli esimene krahv, kes teadaolevalt rajas sinna oma püsiva residentsi, kuna 1089. aasta dokumendis nimetatakse teda "comes Henricus de Lutzeleburg". Aastaks 1083 oli all-linnas kaks kirikut ja kaks silda üle Alzette'i ja Pétrusse'i jõgede. Asukate tegevuseks olid kalapüük, küpsetamine ja jahvatamine. Samal aastal asutati Konrad I poolt lossi taga künkal benediktiiniAltmünsteri klooster.
Luxembourgi linn sai strateegilise väärtusega riigi keskuseks Madalmaades. Selle kindlustusi laiendati ja tugevdati järgnevate omanike poolt aastate jooksul pidevalt, mis tegid sellest ühe tugevama kindluse Euroopas. Oma hirmuäratavate kaitseehitiste tõttu sai see tuntuks kui "Põhjamaa Gibraltar". Luksemburgi krahvid kaotasid Limburgi pärandi, kui nad Brabanti hertsogite poolt 1288. aasta Worringeni lahingus võideti; siiski lahendas krahv Heinrich VII, kelle isa Heinrich VI lahingus tapeti, tüli, kui abiellus aastal 1292 Brabanti Margaretega. Aastal 1308 valiti ta Roomlaste kuningaks ja krooniti aastal 1312 Saksa-Rooma keisriks, esimeseks kolmest keisrist, kes pärinesid Luksemburgi dünastiast. Tema poeg Johann Pime sai aastal 1310 Böömimaa kuningaks, pärast mida viis dünastia oma võimukeskuse Praha linnusesse.