Klubi asutati 1885. aastal nimeMillwall Rovers all. Vaatamata sellele, et klubikodustaadion asus LondonisMillwalli piirkonnas viimati 1910. aastal, on piirkonna nimi klubi nimes säilinud. Kuni 1993. aastani oli klubi kodustaadionNew Crossi piirkonnas asuvThe Old Den. Seejärel koliti oma praegusele kodustaadionile, mis kannab nimeThe Den.
Inglismaa jalgpalliliigas on Millwall mänginud alates 1920. aastast. Suurem osa ajast on mänginud Inglismaa teisel ja kolmandal liigatasemel. Inglismaa kõrgliigas on mängitud vaid aastatel 1988–1990. Hooajal 1988–89 saavutati liigas ajaloo kõrgeim koht, milleks oli kümnes. 2004. aastal jõuti Inglismaa karikavõistlustel finaali, kus kaotati Inglismaa suurklubileManchester United tulemusega 0:3. Sellega kvalifitseeruti esimest korda UEFA Euroopa klubide turniirile – 2004. aastal kaotatiUEFA karika esimeses ringis Ungari klubileFerencvárosile kahe mängu kokkuvõttes tulemusega 2:4.
Millwalli toetajad on tuntud huligaansuse poolest ning klubi toetajate kurikuulsust on kujutatud mitmes mängufilmis. Klubi toetajad on samuti tuntud oma fännilaulu "No one likes us, we don't care" poolest.