O clube nasceu em 1885 como Millwall Rovers, fundado por trabalhadores da fábrica de conservas J.T. Morton na Isle of Dogs, no leste de Londres. Ganhou a Southern League em 1895 e 1896 e se mudou para o outro lado do Tâmisa, para New Cross, em 1910, ano em que também estreou n'O Den original. Joga com o apelido de Os Leões desde que a imprensa o chamou de leão do sul depois de eliminar o líder da primeira divisão, o Aston Villa, na Copa da Inglaterra de 1899-1900.
Entrou para a Football League em 1920 e se firmou como time de copa nas décadas seguintes, com três semifinais da Copa da Inglaterra, em 1900, 1903 e 1937, e o recorde de público do clube, 48.762 pessoas, contra o Derby County em 1937. O Den foi bombardeado na Segunda Guerra, em 1943, e o clube ainda disputou uma final da Copa da Liga de Guerra em Wembley contra o Chelsea, diante do rei George VI, em 1945. O pós-guerra foi de queda, com rebaixamento em 1948 e um pedido de reeleição na Football League em 1950.
Entre 1964 e 1967 o time ficou 59 jogos sem perder em casa, e na temporada de 1971-72 fechou a segunda divisão inteira invicto no próprio campo, o único clube a conseguir isso em quatro divisões diferentes. A fama de torcida hostil ficou marcada em 1985, quando a partida de Copa da Inglaterra contra o Luton Town terminou com 81 feridos em confrontos nas arquibancadas. O acesso à elite veio em 1987-88, como campeão da segunda divisão, e a temporada de 1988-89 fechou em décimo lugar, ainda hoje a melhor campanha do clube na primeira divisão inglesa. Em agosto de 1993 o clube se mudou para o atual Den, a poucos metros do antigo, o primeiro estádio all-seater construído na Inglaterra depois do relatório Taylor sobre a tragédia de Hillsborough.
Uma administração judicial em 1996-97 quase fechou as portas, e o empresário Theo Paphitis assumiu a presidência para estabilizar as contas. Com Dennis Wise como jogador-técnico, o time chegou à primeira grande decisão da história em 2004, perdendo a final da Copa da Inglaterra por 3 a 0 para o Manchester United, e se classificou para a Copa da UEFA, a única campanha europeia do clube.
Kenny Jackett trouxe seis anos de estabilidade a partir de 2007 e voltou à Championship pelo playoff de 2010, e Neil Harris, o maior artilheiro da história, quebrou o recorde de gols do clube em 2009 antes de assumir como técnico em três passagens diferentes. O clube caiu à League One em 2015 e voltou pelo playoff de 2017, seguindo na Championship desde então. Depois da morte do dono John Berylson em 2023, o filho James assumiu a presidência, e em 2025-26, sob Alex Neil, o time fez os 83 pontos mais altos da história do clube na segunda divisão.