Although the band did release the song as a single and filmed a video for it (featuring the band members performing the song on a boat, with a cameo appearance by Kirk Hammett of Metallica, who has been a close friend of Claypool since they attended the same school), the single had very limited success due to its being released on an indie label, and the band did not receive mainstream attention until their next single, "Jerry Was a Race Car Driver", from their 1991 major label debut Sailing the Seas of Cheese. Because of this, many overlook "John the Fisherman" and claim "Jerry Was a Race Car Driver" was Primus' first single. When Frizzle Fry was re-released in 2002, many fans who caught on during the major label days of the band bought the album, and it became a fan favorite. There was a new interest in this song, and it received some radio and MTV airplay.
"John The Fisherman" is the first part of a four-part story called the "Fisherman's Chronicles", which continued on Primus' later albums. Its immediate sequel was "Fish On (Fisherman Chronicles, Chapter II)" on 1991's Sailing the Seas of Cheese, followed by "The Ol' Diamondback Sturgeon (Fisherman's Chronicles, Pt. 3)" on 1993's Pork Soda and most recently "Last Salmon Man (Fisherman's Chronicles, Part IV)" on 2011's Green Naugahyde.
The live version of John The Fisherman that appears on Suck on This contains an intro consisting of the Rush song YYZ.