Kapela Gay for Johnny Depp vznikla v roce 2004 z bývalých členů post-hardcorových kapel Garrison a Instruction a 12. července 2004 vydala svou první nahrávku Erotically Charged Dance Songs for the Desperate. Pětiskladbové EP se setkalo s pozitivními recenzemi, které Gay for Johnny Depp často přirovnávaly ke kolegům z hardcorových kapel The Blood Brothers a The Locust.
Kapela nahrála své druhé EP, Blood: (An Apocalyptic Adventure Beyond Sodom and Gomorrah) v létě 2005 a vydali ho 19. září 2005 na britském labelu Captains Of Industry. To bylo podpořeno malým turné po Velké Británii. Deska získala Gay for Johnny Depp mnoho fanoušků, a to jak díky neobvyklým názvům písní, tak díky hudbě samotné.
Gay for Johnny Depp odehráli svůj vůbec první koncert ve Velké Británii 14. září 2005 v Exeteru jako support skupiny Million Dead. Během koncertu byl frontman Marty Leopard udeřen rozzuřeným davem a musel odjet do nemocnice, kde mu bylo provedeno 5 stehů v obličeji.
Dne 9. června 2006 vystoupili Gay for Johnny Depp na Download Festivalu v Donington Parku ve Velké Británii. V témže roce vyšla jejich píseň Sex In Your Mouth na kompilačním albu Kerrang! s názvem New Breed.
První dlouhohrající album kapely The Politics of Cruelty vyšlo 5. listopadu 2007; bylo vzácným příkladem hardcoreové kapely, která získala pozitivní recenze v publikacích jako NME, Q, The Guardian a Uncut i v těžších rockových publikacích jako Rock Sound. Řada skladeb se také vysílala na BBC Radio 1.
Místo obvyklého biografického materiálu obsahovaly předprodejní kopie alba rozeslané médiím vysoce explicitní pornografický dopis fanoušků herci Johnnymu Deppovi, který údajně napsal někdo známý prostě jako „Brad“. Tento přístup byl v souladu s předchozími propagačními materiály kapely, které obsahovaly lahvičky s amylnitritem, chirurgické gumové rukavice, kondomy, explicitní homosexuální fotografie a další explicitní dopisy od „Brada“.
Debutové album kapely figurovalo v žebříčku NME Top 10 po celý listopad 2007. Tentýž měsíc byl zpěvák Marty pozván k účasti v každoroční rubrice Pub Golf časopisu NME. Ukázky z tohoto večera se následně objevily na internetu.
Gay For Johnny Depp absolvovali v lednu a únoru 2008 a v dubnu 2008 turné po Velké Británii jen v ponožkách zakrývajících intimní partie.
V období od 13. listopadu do 4. prosince 2009 absolvovali další turné po Velké Británii.
Druhé studiové album What Doesn’t Kill You, Eventually Kills You kapela vydala 14. února 2011.
Dne 31. října 2011 vydali na YouTube video a e-mail do svého mailing listu, ve kterém oznámili, že se jejich cesty rozcházejí.
Její druhé EP Blood: The Natural Lubricant (An Apocalyptic Adventure Beyond Sodom and Gomorrah) bylo znovu vydáno v září 2012, tentokrát na vinylu limitovaném na 300 kopií prostřednictvím nezávislého britského labelu Moshtache Records.