Men at Work's second studio album, Cargo, was released in Australia in April 1983, reaching No. 1 on the Australian Kent Music Report Albums Chart. The album's lead single, "Dr. Heckyll & Mr. Jive," was issued in Australia ahead of the album in October 1982 and reached No. 6 on the Kent Music Report Singles Chart. Despite recording having been completed in mid-1982, Cargo's release was held back due to the international commercial success of the band's 1981 debut album, Business as Usual.
"Overkill" was released in April 1983 and debuted on the Billboard Hot 100 chart at No. 28 on 9 April. It peaked at No. 3 in early June. The album's third single, "High Wire", followed in late 1983, peaking at only No. 89 in Australia, and No. 23 on Billboard's Hot Mainstream Rock Tracks. The band toured the world extensively in 1983 to promote the album and related singles. The song was #55 in the year-end Top 100 chart in Canada. 
American alternative rock band Lazlo Bane covered the song and originally released it as a b-side of their debut single "Buttercup" on Fish of Death Records.
After signing with Almo Sounds the song was released as promo single and included on the EPShort Style, and it was later released on the band's debut album 11 Transistor, which came out in January 1997.  As a commercial single "Overkill" was released in some territiries in 1997 and 1998.
The song was recorded with participation of Colin Hay, who plays guitar on the track and sings the last verse solely and last chorus together with Chad Fischer.
The video shows Lazlo Bane playing the song in a large hall of the hotel during the night while disturbing other residents, who were played by the members of the band with Colin Hay playing the front desk clerk. During the first half of the song Hay receives several angry calls about the noise but doesn't do anything about it. During the guitar solo the hotel starts to shake, finally forcing Hay to enter the hall where the band is playing, but only to sing the rest of the song together with the band.
In 2003 Colin Hay released Man @ Work album that consisted of re-recordings of songs from the Men at Work catalog as well as his solo career songs. The album featured an acoustic version of "Overkill". An edited version of that track was previously released in September 2002 on Music from Scrubs, the first NBC series Scrubssoundtrack album. Colin Hay also appeared in the series itself, performing an acoustic version of the song in Season's 2 premiere episode "My Overkill".
^Nimmervoll, Ed. "Men at Work". Howlspace – The Living History of Our Music (Ed Nimmervoll). White Room Electronic Publishing Pty Ltd. Archived from the original on 27 July 2012. Retrieved 20 September 2014.