Durante la dominazione romana, presso l'incrocio di due strade, si ergeva un torrione fortificato, che nel Medioevo apparteneva all'abbazia di San Massimino di Treviri. La fortificazione (castellum) venne chiamata in periodo medioevale Lucilinburhuc (= piccolo castello), da cui ebbe origine, attraverso la forma intermedia Lützelburg, il nome di Lussemburgo, mentre lo sperone roccioso che si innalzava nelle immediate vicinanze (Rupe di Bock) non ne accresceva l'importanza militare.

Nel 963 il castellum passò al conte Sigfrido, che lo trasformò nel suo castello. Sigfrido, detto in seguito di Lussemburgo, è considerato il fondatore della città. Subito dopo venne costruita la nuova cinta muraria e la chiesa di San Nicola, ora Cattedrale. Nel 1340, sotto il regno di Giovanni di Lussemburgo venne realizzata l'ultima cerchia di mura (poi demolita nel 1867). Nel 1447 Lussemburgo fu conquistata dai borgognoni di Filippo III, più tardi entrò a far parte prima dell'Impero spagnolo, poi di quello austriaco.

Sotto la dominazione asburgica le sue fortificazioni vennero ulteriormente rafforzate, facendo così di Lussemburgo una delle più solide roccaforti d'Europa. Furono inoltre costruite casematte ed una ventina di chilometri di gallerie sotterranee. Nei primi anni del XIV secolo il conte Enrico di Lussemburgo divenne l'imperatore Enrico VII e per quasi 150 anni l'impero rimase nelle mani della casata di Lussemburgo.

Durante le guerre rivoluzionarie francesi Lussemburgo fu presa due volte dai francesi, la seconda volta dopo sette mesi d'assedio. La durata dell'assedio fece molto scalpore in Francia e l'ingegnere Lazare Carnot definì Lussemburgo la più imprendibile delle roccaforti del mondo dopo Gibilterra. Con la resa della guarnigione austriaca, Lussemburgo venne annessa alla Francia, all'interno del dipartimento delle Forets. Dopo il 1815 la città ospitò una guarnigione prussiana, sostituita da una olandese una volta ratificato l'ingresso del Lussemburgo nel Regno Unito dei Paesi Bassi. Dopo la crisi lussemburghese, venne stabilita dal trattato di Londra del 1867 la demolizione delle possenti mura cittadine (24 km), demolizione che durò sedici anni e costò un milione e mezzo di franchi d'oro.

Dopo la morte di Guglielmo III e l'indipendenza lussemburghese dai Paesi Bassi con l'ascesa al trono di Adolfo, Lussemburgo divenne la capitale di uno Stato indipendente a tutti gli effetti. Nel XX secolo, con l'allargarsi della città sono stati edificati più di cinquanta ponti, alcuni dei quali veri e propri modelli di ingegneria, come il ponte Adolphe, con l'arcata in pietra a volta più ampia del mondo, che scavalcano i fiumi Alzette e Pétrusse. Nonostante la neutralità, venne occupata dalle truppe dell'Impero tedesco il 2 agosto 1914, il 30 dello stesso mese divenne sede del comando tedesco sul fronte occidentale. Nel 1921 i confini cittadini vennero ampliati con l'annessione delle borgate di Eich, Hamm, Hollerich e Rollingergrund.

Nel 1940 Lussemburgo venne occupata dalla Germania nazista che, nel 1942, l'annetté ai propri territori. Il 10 settembre 1944 fecero il loro ingresso in città le truppe alleate. Dopo il termine del conflitto, Lussemburgo divenne sede di alcune agenzie europee come la Comunità europea del carbone e dell'acciaio, la Corte di giustizia dell'Unione europea, la Corte dei conti europea e la Banca europea degli investimenti.

È in corso la costruzione di un polo giudiziario. Il plateau du Kirchberg è dalla fine degli anni ottanta in piena espansione. Oggi, il palazzo Alcide de Gasperi (detto Bâtiment Tour), le torri A et B – situate al Kirchberg – definiscono, con le fortificazioni, la chiesa Saint-Michel e la cattedrale Notre-Dame, la "skyline" della città di Lussemburgo.