Million Dead came together in London in mid–2001. Cameron Dean (guitar) and Julia Ruzicka (bass) had both come to England from Australia with forming a band in mind. They met and started writing, before roping in Ben Dawson (drums), who had been Cameron's underling in a record store. Ben then called up his old friend Frank Turner who'd been the singer in various bands with him since age 11. The name was chosen from a line in "The Apollo Programme Was a Hoax", a song by Swedish hardcore punk band Refused, and in September of that year they recorded their first demo and began gigging around the UK.

Over the next year support slots were begged and stolen with Cave In, The Eighties Matchbox B–Line Disaster, The Icarus Line and Alec Empire. In late 2002 they came into contact with Integrity Records, and by signing up with them and Xtramile Recordings, they put out their first single, Smiling At Strangers On Trains in February 2003 (for which the video was rarely shown uncut due to scenes of a man wearing a gimp mask, and a homeless man urinating through a letterbox as well as on Dean). This saw support from John Peel, Mike Davies, Mary Anne Hobbs and Steve Lamacq, and was soon followed by a support slot with Pitchshifter on their farewell tour (featuring a gig at the London Astoria which the band have since described several times as their worst ever performance).

April 2003 saw them in Mighty Atom Studios recording their debut album, A Song To Ruin. This was released in September, hot on the heels of second single Breaking The Back and a nomination as "Best Newcomer" in the Kerrang! Awards. More touring with Funeral for a Friend ensued and they rounded off the year with their first headline tour and third single, I Am The Party, which was A–listed by MTV2. In December 2003 they went out on their first headline tour of the UK in support of their 'A Song To Ruin' album with Jarcrew and Minus in tow.

In 2004 they appeared in Austin, Texas for the South by Southwest Festival, and then went out on the road in support of the single I Gave My Eyes To Stevie Wonder, released on May 17th. Original guitarist Cameron left the band to get married, and was replaced by Tom Fowler (ex–Abjure, Pale Horse). After a number of summer festival dates where the band premiered a lot of new material, at the end of 2004, the band retreated into the studio to write and record their second album. Written and recorded in around eight weeks, Harmony No Harmony was finally released in May 2005, preceded by the singles Living The Dream in March 2005 and After The Rush Hour just in advance of the album. The band hit the road for more UK headlining dates, taking the likes of Fighting with Wire, No Hope In New Jersey and The Sound Explosion along for the ride. They went out again immediately after this in April and May to coincide with the release of "Harmony No Harmony", with Days Of Worth and Engerica supporting.

During July 2005, they went out on the road again, this time supporting Finch on several dates of a UK–wide tour, and announced that a new single would be launched in September 2005 to coincide with their next UK headline tour. At the Nottingham gig, the lead singer mentioned he was "currently homeless" and asked the crowd to donate T–Shirts. In August 2005, via a blog on their official website, it was announced that a DVD was in the works, to be titled Schminstrument and released in the autumn. In spite of posts on the messageboard on the band's (now offline) official website, it now seems unlikely this will ever surface.

On September 11th 2005, it was announced via the band's official website that Million Dead were to call it a day at the conclusion of their September tour, as "irreconcilable differences within the band mean that it would be impossible to continue, and anyway, weâ??d rather leave a good–looking corpse. Our reasons are personal and assured.". They played their last ever date at Southampton's Joiners on September 23rd 2005.

Singer Frank Turner quickly reappeared as an acoustic solo artist and has put out an EP called Campfire Punk Rock, two albums: Sleep is for the Week and Love, Ire and Song and split vinyl with Jonah Matranga. Guitarist Tom Fowler and bassist Julia Ruzicka have started Who Owns Death TV (also featuring Rich from also–defunct UK band Cars As Weapons – famed for working with Walter Schreifels). Drummer Ben Dawson is currently drumming for Palehorse, Armed Response Unit and is generally a drummer for hire.