Schoolmates Danny Lilker and Scott Ian formed Anthrax in 1981 in New York City. They both played guitar, but Lilker switched to bass when they could not find a suitable bassist. In 1982, after some lineup rotations, Anthrax added vocalist and fellow schoolmate Neil Turbin. Drummer Charlie Benante and lead guitarist Dan Spitz were added in 1983. Anthrax recorded a five-track demo in early 1983, which led to the band signing with Jon Zazula's Megaforce Records. The label issued a seven-inch single of "Soldiers of Metal / Howling Furies", which sold 3,000 copies in two weeks. Fistful of Metal was recorded in Pyramid Sound Studios in Ithaca, New York and produced by Carl Canedy, drummer in The Rods. The album was released in January 1984 by Megaforce in the US, Music for Nations in the UK, and Roadrunner in Europe.
Shortly after the release of Fistful of Metal, Lilker was fired by Anthrax. In Lilker's own words "After I was thrown out, the guys unfairly said, "Well, it took him 30 times to record the bass track for 'I'm Eighteen,'" and if you listen to the bass track, if you didn't know the whole story, you would say, "Well, that's weird, isn't it?" It's only, like, five notes.". The band, at Ian and Benante's insistence, hired Charlie's nephew, Frank Bello, as Lilker's replacement. Turbin had contributed song ideas, lyrics, titles and arrangements to most songs on the album, as well as three songs from the second album Spreading the Disease, but Ian and Benante, who played guitar in addition to drums, felt they needed tighter control on the songwriting. Due to a songwriting partnership between Ian and Benante, with Ian wanting to be more of a central focal point he began writing the lyrics and Benante the music, Turbin was forced out of the band a few weeks after the Roseland Ballroom show with Metallica. Music journalist Eddie Trunk stated: "Early on, I told Jon Zazula that what I didn't like about Anthrax was singer Neil Turbin's vocals." He admits in his writing to pressuring Zazula and Anthrax into firing Turbin from the band. The band did not rehire Lilker when given the opportunity and instead opted for then Anthrax roadie Frank Bello.