In 1981, guitarists Rich Conte and Bobby Gustafson joined the band. At this point, the band started writing original songs, including "Grave Robbers" (later renamed "Raise The Dead"), "Overkill", and "Unleash The Beast (Within)". More songs would follow, including "Death Rider" (1981) and "Rotten To The Core" (1982). In 1983 Conte left and Bobby Gustafson remained as the sole guitarist. The band became a staple at New York and New Jersey clubs, such as L'Amours. Verni gave Ellsworth the nickname "Blitz" due to his over-the-top lifestyle, a lifestyle that once earned Ellsworth an ejection from the band for a few days in 1983. Around this time, the classic green logo was adopted, which Rat Skates specifically designed to stand out on a poster loaded with red and black logos of the other bands on the bill.

In 1983, the lineup of Rat Skates, D.D. Verni, Bobby Gustafson and Bobby Blitz, released the Power In Black demo, a recording that made as much impact in the underground tape trading circuit as demos by up-and-coming Bay area thrash bands like Exodus and Testament. Power In Black gained the band two compilation appearances, 'Feel The Fire' was included on "New York Metal '84" and 'Death Rider' appeared on volume V of the legendary Metal Massacre series. The band was also able to secure a small recording deal with Azra/Metal Storm Records that resulted in the 1984 four track EP Overkill, that quickly sold out, instantly pushing the band to the forefront of the fledgling thrash metal movement. Though it is said that the band never saw any money from the release, the Overkill EP garnered the band massive underground interest, and the attention of Jon Zazula, the owner of Megaforce Records, one of the most prominent independent heavy metal record labels at the time. Megaforce signed Overkill to a new multi-album record contract and released their full length debut album Feel The Fire in 1985. Hailed by many critics and fans as a thrash metal masterpiece, the album cemented the band's position as one of the driving forces of the east coast thrash movement. The band spent the better part of 1985 and 1986 touring in support of Feel The Fire, beginning as support act for Megadeth's "Peace Sells" US tour and later in Europe with Anthrax and Agent Steel.

1987 marked the release of Overkill's second album Taking Over, the first to be released by Megaforce in cooperation with the major label Atlantic Records. The album featured improved song writing and production and had a somewhat more epic style, showcased in such songs as the anthemic "In Union We Stand". The song was chosen to be Overkill's first music video, used to promote the band through the booming new medium of music television. Another European tour followed, this time opening for Helloween.

Late in 1987, the !!!Fuck You!!! EP was released, consisting of a studio recording of 'Fuck You as well as a handful of live tracks recorded earlier that year in Cleveland. 1987 also saw the departure of drummer Rat Skates. He was replaced by Mark Archibole for a few gigs, then on a permanent basis by European drummer Bob "Sid" Falck previously of Paul Di'Anno's Battlezone.

Overkill released the follow-up to Taking Over, the aptly titled Under the Influence, in 1988. Once again produced by Alex Perialas, Under the Influence was much more raw and thrashy, lacking most of the grand and epic atmosphere of its predecessor. Suffering from rushed writing and production, the album is often regarded as a snapshot and a step backwards for the band. The song "Hello From The Gutter" was released as a single, and the music video gained regular airplay on MTV's Headbangers Ball. Overkill kept up constant touring all over the world, furthering their reputation as one of the most active live metal bands.

Overkill released their breakthrough album The Years of Decay in 1989. It was recorded with famed producer Terry Date (Pantera, White Zombie, Soundgarden) and featured the band's best production to date. It mixed the raw approach of "Under The Influence" with more complex song structures and epic elements, resulting in a more serious atmosphere and longer songs, including the eight minute title track and the ten minute "Playing With Spiders/Skullkrusher." The uptempo thrasher "Elimination" was released as a single and the music video again received regular airplay on MTV's Headbangers Ball. The song became a fan favorite and would be played live at every show, even 20 years later. Live support of The Years of Decay took place, in part, on a tour called "Dawn Of The Decade" together with label mates Testament.

In 1990, guitarist and songwriter Bobby Gustafson left the band. Verni and Gustafson had long locked horns over the direction of the band, and in the end Blitz sided with Verni, asking Gustafson to leave Overkill. The remaining members added two new guitarists to the band; Rob Cannavino who had been Gustafson's guitar technician, and Merritt Gant, from the New Jersey thrash band Faith Or Fear.

The 'new' Overkill recorded their fifth album Horrorscope, again with Terry Date, in 1991. Featuring the furious riffs and trade-off solos of new guitarists Cannavino and Gant, and the refined songwriting of Verni and Ellsworth, Horrorscope quickly silenced fan fears that the loss of a chief songwriter would ruin the band. Today, the album is widely regarded as one of the Overkill's defining moments and is arguably their heaviest release. Focusing on a darker, heavier style, the album spawned the doomy single "Horrorscope", a departure from the band's earlier singles, which had traditionally been uptempo songs. The band continued to tour constantly, fully cementing their reputation as one of the premier live bands of the genre.

In 1992, during the Horrorscope tour, Sid Falck left the band. Admittedly never a big fan of thrash metal music, Sid said that he had initially wanted to push his drumming to the limit by playing the most complex type of music (of the era), and in time he decided to pursue other musical interests.

Sid was replaced by M.O.D. drummer Tim Mallare, with whom the 1993 album I Hear Black was recorded. Produced by Alex Perialas (who by now had worked with Anthrax and Testament), I Hear Black was the first Overkill album released directly through Atlantic Records. The album once again presented a change in style, from the heavy thrash of Horrorscope to a more Stoner song oriented style influenced by Black Sabbath and Blues. The eclectic nature of the album is often attributed to the fact that many different song writers were involved. Verni and Ellsworth would handle most of the song writing themselves on subsequent albums, with only minor contributions from the other members. A music video was shot for "Spiritual Void" but failed to receive much airplay. The European leg of the 1993 "World Of Hurt Tour" featured Savatage and Non-Fiction as support acts.

Overkill's self-produced seventh album W.F.O. (which stands for "Wide Fuckin' Open", a common biker term) was released in September 1994 as an answer to the criticism that I Hear Black had received. The album presented a fast, heads-down, old school thrash metal style without any of the experimental elements present on the previous record. The music video for "Fast Junkie" was widely ignored by MTV, due to changing mainstream tastes and limited airplay availability for metal bands. Overkill continued to have bigger success overseas, mounting an extensive European tour in the fall, supported by Jag Panzer and Massacra.

With Grunge dominating the airwaves in the US, and many heavy metal radio stations changing formats, W.F.O. failed to find an audience and in 1995 Overkill was dropped by Atlantic Records. Overkill were happy to be let go from the mainstream label, where they felt they received little or no attention and signed to different record companies around the world (CMC International in the US).

A March 1995 show, once again in Cleveland, Ohio, was recorded for Overkill's first full-length live album, a 100-minute double CD entitled Wrecking Your Neck. The album was released in April 1995, with the first pressing featuring a bonus CD containing the Overkill EP that had been out of print for ten years. A music video for the song "Bastard Nation" taken from Wrecking Your Neck was also released, but again failed to receive airplay in the US.

Late in 1995, both Cannavino and Gant decided to leave the band; Rob Cannavino to focus on motorcycle racing, and Merritt Gant to spend more time with his family. To everyone's surprise, Overkill then hired Joe Comeau, former singer of Liege Lord (now playing guitar). Comeau brought along former Anvil guitarist Sebastian Marino, with whom he had worked with in the past. The new line up recorded The Killing Kind in 1996, again self-produced and mixed by Chris Tsangarides (Judas Priest). While staying well within the thrash genre, the album was a departure from its predecessor's more traditional thrash metal style and featured many modern elements, such as Hardcore elements, while the vocals showed influences from a broad spectrum of music. As Comeau was also a singer, backing vocals on The Killing Kind and subsequent albums were more elaborate and frequent than before, adding another new element to the band's sound. Press response to The Killing Kind was very positive, but the album remains a hotly contested topic among the band's audience, with some longtime fans resistant to the new modern elements, and others hailing The Killing Kind as one of the band's finest moments.

Overkill toured Europe twice in support of The Killing Kind first in February 1996 with Megora and Accu§er, and then again in November with Anvil and Stahlhammer. In the summer of 1996, Overkill appeared on Volume 2 of Century Media's "Legends Of Metal - A Tribute To Judas Priest" compilation, to which they contributed 'Tyrant', heavily adapted to the band's own style.

In summer 1997, the band released !!!Fuck You!!! and Then Some. The album included the !!!Fuck You!!! EP, which had been out of print for some years, along with the classic Overkill EP and two live tracks from a 1990 promo single. October of the same year saw the release of the ninth Overkill studio album, titled From The Underground And Below. This record retained some of the modern influences from The Killing Kind, while also reincorporating elements from the band's earlier efforts. Some songs on From The Underground And Below, including "Save Me", even had a slight industrial metal sound to them. Reportedly a video for the track "Long Time Dyin'" was shot, but due to the non-existence of metal in the mainstream media at the time, it is unlikely that the video has ever aired on television. Again Overkill opted to only tour Europe in support of the album, which took place in May 1998, with Nevermore, Angel Dust and Nocturnal Rites.

In 1998, Blitz was diagnosed with a very aggressive form of nose cancer and underwent immediate surgery, thankfully in time to catch the cancer before it spread. After his recovery, the band started work on their tenth studio album, and the self produced Necroshine was released in February 1999, making Overkill the very first thrash metal band ever to release ten full-length studio albums (Other first wave thrash bands, such as Sodom or Kreator would not achieve this milestone until two years later). While once again quite different from the previous records and musically not considered "classic" Overkill, the album was vocally even more experimental than The Killing Kind, and was well received by fans and critics alike.

Soon after the release of Necroshine, Sebastian Marino left Overkill to spend more time with his family. He was replaced by Dave Linsk from the New Jersey hardcore/thrash metal band Anger On Anger. A two-week European trip in June was arranged to fill the gap between appearances at the Dynamo and With Full Force festivals.

September 1999 saw the release of Coverkill, an album consisting entirely of cover versions from bands that were especially influential to Overkill, such as Black Sabbath (featured no less than three times), Kiss, Motörhead, Manowar, and The Ramones. Some of the tracks had been previously available on compilations or as Japanese bonus tracks, but others had been shelved for years (the earliest recording was from the Under the Influence sessions) or were recorded immediately prior to the album's release. A full European tour in support of both Necroshine and Coverkill took place in February 2000, as Overkill co-headlined with Canadian thrash metal band Annihilator, with the German band Dew-Scented in the opening slot.

During the European tour, Annihilator fired their singer Randy Rampage due to his disruptive behavior. A few months later, Overkill's Joe Comeau was confirmed as his replacement, effectively ending his tenure with the band. Overkill returned to the studio, this time as a four piece, and in the fall of 2000 released Bloodletting. Once again produced by the band, and mixed this time by Colin Richardson.

November of the same year saw the band again touring Europe as a special guest of Halford's "Resurrection" world tour. Since Overkill had not found a new second guitarist yet, Joe Comeau joined on a temporary basis for the tour. For the last couple of shows, the band also utilized another session musician. With D.D. Verni's wife about to give birth to their second child, D.D. was replaced temporarily by Derek "The Skull" Tailer, the bass player in Dee Snider's band S.M.F. In early 2001, Tailer was announced as a permanent member of Overkill, although not on bass guitar, but filling the vacant spot on guitar.

After taking a break, Overkill resurfaced in 2002 with Wrecking Everything, their second full-length live album, recorded at the Paramount Theatre in Asbury Park, New Jersey. The album contained only songs that had not been on Wrecking Your Neck, some simply because they were released on later albums, but also a few early songs from albums such as Taking Over and Under the Influence. The same show was used for Overkill's first ever DVD, Wrecking Everything - An Evening In Asbury Park, also released in 2002.

The European tour in June 2002, supporting both Bloodletting. and Wrecking Everything saw Blaze and Wicked Mystic opening up for Overkill. During the second to last show of the tour in Nuremberg, Germany, Blitz suffered a stroke on stage and collapsed. For nearly three days, rumors ran rampant, reporting everything from Blitz being in a coma, permanently paralyzed, or even that Blitz had died. Finally, three days later, the band announced that the stroke was very minor and had no lasting consequences, as well as no cause that could be determined by the doctors.

Overkill entered the studio in late 2002 to record their next studio album, Killbox 13. Produced by the band and Colin Richardson and released in March 2003, the album was actually only their twelfth regular studio album, but the Overkill EP was also counted to achieve the number 13. The album received critical acclaim, combining the "new" Overkill with their raw early style as presented on the debut album Feel The Fire. Touring for the album included a number of European festivals during the summer, and a full European tour followed in November with Seven Witches and After All. The band played without Derek Tailer, who was absent for undisclosed reasons. Nobody was hired to fill in for him, so Overkill toured as a four-piece for the first time since 1990. Tailer was still considered a full member of the band.

In late 2004, after a Japanese tour with Death Angel and Flotsam and Jetsam, the band started work on another record in D.D. Verni's own recording studio. The album, ReliXIV, was produced and mixed by the band themselves and released in March 2005.

Overkill toured the eastern US in April 2005, and just before they went on a European tour in May, it was announced that Tim Mallare would not take part in this tour; replacing him was former Hades drummer Ron Lipnicki. A few weeks later, the band announced that Mallare had left the band on a permanent basis and Lipnicki was his replacement. In the summer of 2005, Overkill organized their first US west coast tour in more than ten years, playing Western Canada to Southern California. The tour was such a success that the band was added to the 2006 Gigantour bill, as second stage headliners, marking Overkill's first nationwide US tour since 1994.

Now with Bodog Music, the band rejoined forces with Jonny and Marsha Zazula, previous owners of Megaforce Records, who are now part of the Bodog Team in the United States. Overkill unleashed its 15th studio album, Immortalis, on October 9, 2007. The album featured Overkill's latest lineup, which, along with founders Bobby "Blitz" Ellsworth and D.D. Verni, includes guitarists Derek Tailer and Dave Linsk, as well as the newest member to join the band, drummer Ron Lipnicki. Lamb Of God vocalist Randy Blythe contributed vocals on the song "Skull And Bones".

On October 30, 2009, it was reported that Overkill had inked a multi-album deal with Nuclear Blast Records. The band's next album, Ironbound ? which is described as a true "thrasher-piece" ? is scheduled for release on January 29, 2010.