After Dogbowl’s departure, Hall asked Bongwater guitarist Dave Rick to help him put together a new band. Rick recruited multi-instrumentalist Chris Xefos, and Hall retained Dansiger on drums. Hall dubbed the new lineup King Missile, dropping the parenthetical “Dog Fly Religion” subtitle “since that was idea.” In late 1989 and early 1990, the band recorded the album Mystical Shit, and in 1990 released it on Shimmy Disc. On the strength of the single “Jesus Was Way Cool,” the album hit No. 1 on the CMJ charts, and the band was signed by a major label, Atlantic Records. This series of events led Hall to make a habit of joking, “‘Jesus’ got me signed to Atlantic Records.” Around this time, King Missile was featured in the 1990 documentary CutTime which chronicled the East Village music scene of 1990.
Another lineup change occurred before the recording of King Missile’s major-label debut, as Dansiger left the band and was replaced on drums by Hypnolovewheel member David Ramirez. The subsequent album, The Way to Salvation, was released on April 16, 1991, and reached No. 2 on the CMJ charts. Atlantic promoted the album with the release of a single, “My Heart Is a Flower,” and accompanying video.
After Ramirez left the group and was replaced by yet another drummer, Roger Murdock, the band recorded its second major-label album, Happy Hour, released on December 15, 1992. The album debuted at No. 1 on the CMJ charts, and its accompanying first single, “Detachable Penis,” became a modest hit, reaching No. 25 on the Billboard Modern Rock Tracks chart. Atlantic released videos for “Detachable Penis” and the subsequent singles “(Why Are We) Trapped?” and “Martin Scorsese,” but neither follow-up single achieved the chart success of “Detachable Penis.” According to Hall, the band realized that its hit song had drawn in many casual fans who didn’t care about the rest of the group’s material; thus, the band began to play the song “early in the set, so that the people who didn’t like us could leave, and we could play for the people who cared. That worked out well. People did leave.”
The band’s third and final album for Atlantic was the eponymous King Missile, released April 19, 1994. Neither the album nor its lead single, “Love Is…,” was a commercial success; consequently, the band was dropped from Atlantic, and broke up shortly thereafter because, according to Hall, “there was no reason to stay together.”