Klubben blev dannet i 1885 under navnet Millwall Rovers af en grupper arbejdere på en lokal fabrik. Klubben ændrede i 1899 navn til Millwall Athletic efter at de havde flyttet til et stadium kaldet The Athletic Grounds. Klubben spillede i perioden i Southern League, som de vandt to gange.[1]
Millwall droppede snart Athletic fra deres navn, og havde dermed deres moderne navn. Klubben blev i 1920 medlemmer af English Football League. Klubben rykkede i 1928 op i Second Division. Klubben var over de næste år liggende mellem Second og Third division før at de i slutningen af 1930erne havde samlet et stærkt hold, som var konkurrencedygtige om oprykning til First Division. Denne ambition gik dog i vasken som resultat af at anden verdenskrig aflyste fodbold.[2]
Millwall rykkede i 1948 ned til Third Division, og var over de næste år et fast hold i den tredjebedste række. Det var frem til 1958 hvor at Millwall rykkede ned i den nyoprettet Fourth Division. Det lykkedes dog at vende klubbens resultater i løbet af 1960erne, og klubben var tilbage i Second Division i 1968. Klubben var over de næste år flere gange tæt på at rykke op i First Division, men det lykkedes dog aldrig, og de rykkede ned igen i 1978.[1]
Klubben stærkeste periode var i 1980erne, og i 1987-88 sæsonen lykkedes det for første gang klubben at rykke op i den bedste række. Det blev dog kun til 2 sæsoner den bedste række før nedrykning i 1990. Perioden efter nedrykning var dog ikke nem, da klubben døjede med financielle problemer, som resulterede i nedrykning igen i 1996.[1]
Klubben har siden været en klub der har varieret mellem at spille i den anden- og tredjebedste rækker, dog har den over den seneste periode skabt stabilitet i Championship.[1]
