The band was formed in 1979 by brothers Rob Wright (bass guitar, vocals, and occasionally guitar) and John Wright (drums, keyboards and vocals). Their name derives from an anti–date rape slogan. For their first four years the duo's music would seem to be influenced as much by jazz and progressive rock as punk rock. The musical press described their earliest recordings as "Devo on a jazz trip, Motörhead after art school, or Wire on psychotic steroids." Nomeansno have been credited with being an influence on, and perhaps even the genesis of, math rock.

The brothers Wright began recording as a two–piece in their parents' basement in 1979. These recordings, heard on their first two self–released 7"s, consisted of full rock band arrangements and had a new wave, warped–pop sound, different from subsequent recordings. When, in the early 1980s, the duo began gigging simply with bass, drums and vocals, the present form of their distinct sound slowly took shape. The songs they played in this period are documented on the Mama LP (re–released in 2004 on their own Wrong Records).

In 1983, they added Andy Kerr (who played with John Wright in Infamous Scientists) on guitar and vocals. Kerr preferred pseudonymity and used such pseudonyms as "Buttercup" or "None–Of–Your–Fucking–Business". He brought a distinct hardcore punk edge to the group, and stayed until 1992. He is often erroneously credited for penning the lyrics of Nomeansno songs on which he sang, perhaps due to deliberately vague liner notes and frequent vocal moonlighting (Kerr sings lead or co–lead vocals on nearly half the songs on Wrong for example). Kerr's vocals were a necessity for a period of time in the 1980s when Rob Wright was recovering from nodules on his vocal cords. While Rob Wright is the band's lyricist and main songwriter, all members have contributed songs to Nomeansno records, and nearly all their material is credited to the entire band.

Wrong is widely considered the band's best and most representative record. ("The playing is incredibly skilled, with the Wright brothers effortlessly shifting tempos and time signatures and Kerr's razor sharp lyrics clicking right into place.")

After Kerr's departure, the Wright brothers recorded Why Do They Call Me Mr. Happy– as a duo. They subsequently recruited guitarist Tom Holliston from Showbusiness Giants and The Hanson Brothers, and have continued touring and releasing records, including Worldhood of the World (As Such), Dance of the Headless Bourgeoisie, One, and All Roads Lead to Ausfahrt, which was released on August 22, 2006. The album was released by AntAcidAudio in the United States and Southern Records in Europe.

The album One, released in 2000, featured "two stunning covers that only make sense coming from Nomeansno": a slow stoner rock–styled version of The Ramones' "Beat on the Brat", and rather authentic fifteen–minute version of Miles Davis' "Bitches Brew" (complete with electric piano and congas), featuring lyrics by Rob.

Nomeansno initially released records with seminal punk rock record label Alternative Tentacles. This relationship ended in 2002 and the band has since reissued old albums under their own Wrong Records imprint through Southern Records.