The magazine was first published in 1984 by Debi Sundahl and Myrna Elana, with the contributions of Susie Bright, Nan Kinney, Honey Lee Cottrell, Dawn Lewis, Happy Hyder, Tee Corinne, Jewelle Gomez, Judith Stein, Joan Nestle, Pat Califia, Morgan Gwenwald, Katie Niles, Noreen Scully, Sarita Johnson, and many others. Susie Bright became editor-in-chief for the next six years. "On Our Backs" defined the look and politics of lesbian culture for the 80s, as well as playing a definitive role in the feminist sex wars of the period, taking the side of sex-positive feminism.
The title of the magazine was a satirical reference to Off Our Backs, a long-running feminist newspaper that published the work of many anti-pornography feminists during the 1980s, and which the founders of On Our Backs considered prudish about sexuality.
In 1985, Sundahl and Kinney spun off the first in a series of precedent-making lesbian erotic videos, called Fatale Video.
In 1994, the magazine experienced financial problems, and, after being bought out by a new publisher, Melissa Murphy (who released only one issue), disappeared from the market until 1998. H.A.F. Publishing then owned the magazine. The original creators moved on to other projects.
In 1997, a photography book based on the pioneering work of On Our Back's artists called Nothing but the Girl was published by Cassell Press, edited by Susie Bright and Jill Posener.