El club fue fundado oficialmente en 1885 bajo el nombre de Millwall Rovers por los trabajadores industriales de la fábrica de conservas alimenticias JT Morton, ubicada en el muelle de Millwall en la Isla de Perros (Isle of Dogs), en el este de Londres (Inglaterra, en un pronunciado meandro del río Támesis). Nació con el firme propósito de canalizar el asociacionismo deportivo y forjar un equipo de fútbol de asociación que representase el orgullo obrero y portuario del East End londinense. Liderados por operarios escoceses de la fábrica e industriales locales como James Morton, el equipo comenzó a disputar sus partidos en un terreno barroso cercano a los muelles del Támesis, adoptando el color azul oscuro en honor a la selección nacional de Escocia.
En 1910, acuciado por problemas de espacio y la expiración de contratos en los muelles del este, el club tomó la trascendental decisión de mudarse al sur del río Támesis, en el barrio obrero de Bermondsey. El histórico estadio de The Den fue diseñado por el famoso arquitecto Archibald Leitch e inaugurado en octubre de 1910. The Den se convirtió rápidamente en uno de los estadios más hostiles, temidos e inconfundibles de Inglaterra, sirviendo como el estadio indiscutido donde nació el apodo oficial de 'Los Leones' por su garra en el juego y la lealtad extrema de su apasionada hinchada.
La temporada 1987-88 se inscribe como uno de los capítulos más memorables de la historia del club. Bajo la férrea conducción técnica de John Docherty, Millwall conquistó el título de la Second Division y logró el ascenso a la Primera División del fútbol inglés por primera vez en su historia. Liderados en la delantera por la inolvidable y emblemática dupla goleadora de Teddy Sheringham y Tony Cascarino, los 'Lions' sorprendieron a todo el país al llegar a liderar la máxima categoría en el inicio de la temporada siguiente, compitiendo de tú a tú con las máximas potencias.
El 22 de mayo de 2004, en el Millennium Stadium de Cardiff, Millwall disputó la final de la FA Cup por primera vez en su historia militar en la segunda división inglesa. Dirigidos por el exjugadorDennis Wise (quien actuaba como jugador-entrenador) y guiados en el terreno por un jovencísimo Tim Cahill, el equipo batalló con coraje y cayó con absoluta dignidad ante el destacado Manchester United de Sir Alex Ferguson. Esta notable gesta copera les permitió clasificar por primera vez a competiciones continentales oficiales de la Copa de la UEFA de la temporada siguiente.