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 and 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 music video for "Overkill" is set up as if the camera is rolling. It starts out at a highway in Australia and moves to show lead singer Colin Hay. He then does a head-snap to the introductory drums. The verse comes in and he starts walking along the railing. He then gets up on the railing and looks like he's going to jump but then gets down. He then walks over and walks past Ron Strykert and John Rees having a conversation. Then he continues walking and then he walks past the camera. Then it goes to a side view of his face as he sings the first line of the chorus. Then it fades into his eyes just to go back to a full view of his side singing the second line of the chorus. Then it goes to a view of his face as he turns away from the camera. Then he turns to a second camera. After that he is walking along sidewalk of the street then crosses. While crossing he stops in the middle of the road to say, " Smell the desperation." Then he walks out of a place while passing a very lit up street. He stops to look through a restaurant window. Again he turns away from camera one and turns to camera two. He sings sideways to the camera while slides of pictures of the street appear in the background. Then he turns to the camera. Then it shows a close up of the guitar playing the solo. Then it shows a close up of the saxophone. Then a camera is on the ceiling while he jumps on the bed screaming the verse. Then they go to a chair where he finishes singing the verse. Then he leaves his room to go upstairs and outside. Then it finishes with him overlooking the city from his balcony. The video was mostly shot in the Melbourne suburb of St Kilda.
Americanalternative rock band Lazlo Bane covered the song for their debut record, the EPShort Style released in 1996, and it was later released on the band's debut album 11 Transistor, which came out in January 1997.  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.