Their name was taken from a scene in the film Rock 'N' Roll High School, in which a laboratory mouse spontaneously explodes upon being exposed to the music of The Ramones, the band's foremost influence. Other major influences include Rocket to Russia and Radio Birdman.
Exploding White Mice got its start in 1983 in Adelaide when Paul Gilchrist (vocals) played a one-off show as a cover band with Andy MacQueen (bass), Gerry Barrett (guitar) and Craig Rodda (drums) at a party. It was Paul's first band; Andy had previously been in the bands The Deviants and the Crunch Pets, and Craig drummed for the Screaming Believers. The show went well enough that the group decided to play together regularly. One of these shows was attended by Giles Barrow, who was the guitarist for the bands Zippy & The Coneheads and Kaos. He ended up joining the group on rhythm guitar. In 1984 they began playing regularly in Adelaide at the Cathedral Hotel; Gerry left near year's end and was replaced by former Spitfire and Tombstone Shadow member Jeff Stephens.
At this point in the group's history, they were primarily still a cover band, but soon after began working on originals. After adding another former member of Zippy & the Coneheads, David Bunney, the group released an EP, 1985's A Nest of Vipers, on Australia's Greasy Pop Records. Sydney rock publication RAM named the album the best Australian record of the year in 1986.