Utworzony z byłych członków post-hardcore’owych zespołów Garrison i Instruction w 2004 roku, Gay for Johnny Depp wydał swoje pierwsze nagranie, Erotically Charged Dance Songs for the Desperate, 12 lipca 2004 roku. 5-track EP spotkał się z pozytywnymi recenzjami, które często porównywane Gay for Johnny Depp do kolegów hardcore zespoły The Blood Brothers i The Locust.
Zespół nagrał swoją drugą EP, Blood: The Natural Lubricant (An Apocalyptic Adventure Beyond Sodom and Gomorrah), latem 2005 roku, i wydali ją 19 września 2005 roku w brytyjskiej wytwórni Captains Of Industry. To było wspierane przez małą trasę koncertową po Wielkiej Brytanii. Płyta zyskała Gay for Johnny Depp wielu fanów, ze względu na nietypowe tytuły piosenek, jak również samej muzyki.
Gay for Johnny Depp zagrał swój pierwszy w historii Wielkiej Brytanii koncert 14 września 2005 w Exeter, wspierając Million Dead. Podczas koncertu, frontman Marty Leopard został uderzony przez wściekłego członka tłumu i musiał udać się do szpitala, aby otrzymać 5 szwów na twarzy.
9 czerwca 2006 Gay for Johnny Depp zagrał na Download Festival w Donington Park, UK. W tym samym roku, ich piosenka Sex In Your Mouth została wydana na albumie kompilacyjnym Kerrang!, New Breed.
Pierwszy długogrający album zespołu, The Politics of Cruelty, został wydany 5 listopada 2007; był to rzadki przykład hardcore’owego zespołu otrzymującego pozytywne recenzje w publikacjach takich jak NME, Q, The Guardian i Uncut, jak również cięższych rockowych publikacji takich jak Rock Sound. Kilka utworów zostało również wyemitowanych w BBC Radio 1.
Zamiast zwykłego materiału biograficznego, przedpremierowe kopie albumu wysłane do mediów zawierały bardzo wyraźny pornograficzny list do aktora Johnny’ego Deppa, rzekomo napisany przez kogoś znanego po prostu jako 'Brad’. Takie podejście było zgodne z wcześniejszych materiałów promocyjnych zespołu, które zawierały butelki azotynu amylu, chirurgiczne rękawice gumowe, prezerwatywy, wyraźne zdjęcia homoseksualne i dalsze wyraźne listy od 'Brad’.
Debiutancki album zespołu pojawił się na liście przebojów NME Top 10 w listopadzie 2007 roku. W tym samym miesiącu wokalista Marty został zaproszony do wzięcia udziału w corocznej funkcji Pub Golf NME. Highlights of the evening have subsequently appeared on the internet.
Gay For Johnny Depp toured the UK in January and February 2008 and in April 2008 wearing nothing but socks on covering their private parts.
They toured the UK again between 13th Nov and 4th Dec 2009.
Drugi studyjny album zespołu, What Doesn’t Kill You, Eventually Kills You, został wydany 14 lutego 2011 roku.
W dniu 31 października 2011 roku zespół opublikował film na YouTube oraz e-mail do swojej listy mailingowej, w którym ogłosił, że ich drogi się rozchodzą.
Druga EP-ka, Blood: The Natural Lubricant (An Apocalyptic Adventure Beyond Sodom and Gomorrah) została ponownie wydana we wrześniu 2012 roku, tym razem na winylu limitowanym do 300 kopii przez niezależną brytyjską wytwórnię Moshtache Records.