Gay for Johnny Depp wurde 2004 aus ehemaligen Mitgliedern der Post-Hardcore-Bands Garrison und Instruction gegründet und veröffentlichte am 12. Juli 2004 ihr erstes Album Erotically Charged Dance Songs for the Desperate. Die 5-Track-EP wurde mit positiven Kritiken bedacht, die Gay for Johnny Depp oft mit anderen Hardcore-Bands wie The Blood Brothers und The Locust verglichen.
Die Band nahm ihre zweite EP, Blood: The Natural Lubricant (An Apocalyptic Adventure Beyond Sodom and Gomorrah), im Sommer 2005 auf und veröffentlichte sie am 19. September 2005 über das britische Label Captains Of Industry. Das Album wurde von einer kleinen Tournee durch das Vereinigte Königreich begleitet. Die Platte brachte Gay for Johnny Depp eine Menge Fans ein, sowohl wegen der ungewöhnlichen Songtitel als auch wegen der Musik selbst.
Gay for Johnny Depp spielten ihr erstes Konzert in Großbritannien am 14. September 2005 in Exeter als Support von Million Dead. Während der Show wurde Frontmann Marty Leopard von einem wütenden Zuschauer geschlagen und musste im Krankenhaus mit 5 Stichen im Gesicht genäht werden.
Am 9. Juni 2006 spielten Gay for Johnny Depp auf dem Download Festival in Donington Park, UK. Im selben Jahr wurde ihr Song Sex In Your Mouth auf dem Kerrang!-Compilation-Album New Breed veröffentlicht.
Das erste Album der Band, The Politics of Cruelty, wurde am 5. November 2007 veröffentlicht; es war ein seltenes Beispiel für eine Hardcore-Band, die positive Kritiken in Publikationen wie NME, Q, The Guardian und Uncut sowie in schwereren Rock-Publikationen wie Rock Sound erhielt. Eine Reihe von Tracks wurde auch auf BBC Radio 1 ausgestrahlt.
Anstatt des üblichen biografischen Materials enthielten die an die Medien verschickten Vorabkopien des Albums einen sehr expliziten pornografischen Fanbrief an den Schauspieler Johnny Depp, der angeblich von einer Person geschrieben wurde, die einfach als „Brad“ bekannt ist. Diese Vorgehensweise entsprach dem früheren Werbematerial der Band, das Flaschen mit Amylnitrit, chirurgische Gummihandschuhe, Kondome, explizite homosexuelle Fotos und weitere explizite Briefe von „Brad“ enthielt.
Das Debütalbum der Band war den ganzen November 2007 über in den NME Top 10 Charts vertreten. Im selben Monat wurde Sänger Marty eingeladen, an der jährlichen Pub-Golf-Sendung des NME teilzunehmen. Höhepunkte des Abends sind später im Internet aufgetaucht.
Gay For Johnny Depp tourten im Januar und Februar 2008 und im April 2008 durch Großbritannien und trugen dabei nichts als Socken, die ihre Geschlechtsteile bedeckten.
Zwischen dem 13. November und 4. Dezember 2009 tourten sie erneut durch Großbritannien.
Das zweite Studioalbum der Band, What Doesn’t Kill You, Eventually Kills You, wurde am 14. Februar 2011 veröffentlicht.
Am 31. Oktober 2011 veröffentlichten sie ein YouTube-Video und eine E-Mail an ihre Mailingliste, in der sie ankündigten, dass sie getrennte Wege gehen.
Ihre zweite EP, Blood: The Natural Lubricant (An Apocalyptic Adventure Beyond Sodom and Gomorrah) wurde im September 2012 wiederveröffentlicht, diesmal auf Vinyl, limitiert auf 300 Exemplare über das unabhängige britische Label Moshtache Records.