High school friends Hock and Genuardi met Walsh through Rama Mayo, owner of indie label Big Wheel Recreation Records. They started the band in the fall of 1998, with Cave and Colby eventually joining later.

They pressed 250 copies of a demo before going on tour with Kid Dynamite. A roadie gave the demo to indie rock label Jade Tree Records, who signed the band and put out a self-titled EP containing all the demo tracks in 2000.

Their debut full-length, Flash Flash Flash on Jade Tree, was released to glowing reviews. Spin Magazine named it as one of the best 20 albums of 2000, and later named the band one of the top 10 punk acts of 2001. The Explosion also came in 2nd for Best Local Punk Act in the Boston Phoenix. They began touring the USA and Europe with the likes of Sick of it All, AFI (A Fire Inside), Avail, Leatherface, US Bombs, Alkaline Trio, The Queers, Social Distortion, and Joe Strummer and the Mescaleros. They were also featured on the 2001 and 2005 Warped Tour.

Unfortunately, they quickly faced a problem. Genaurdi's former straight edge hardcore band, In My Eyes, had been signed to Revelation Records. Revelation Records threatened to sue Genaurdi if he was credited on any of The Explosion's records, believing that The Explosion's success with Jade Tree should belong to them. The Explosion settled the dispute by writing an EP for Revelation, sarcastically titled Steal This. In 2003, they released an EP called Sick of Modern Art on their own label, Tarantulas Records.

Seven major labels soon became involved in a bidding war over The Explosion. They were eventually signed to Virgin Records, who distributed Sick of Modern Art. Their album Black Tape was released on Virgin in the United States on October 5, 2004 and on March 15 in the U.K.