Gay for Johnny Depp blev dannet af tidligere medlemmer af post-hardcore-bandene Garrison og Instruction i 2004 og udgav deres første pladeindspilning, Erotically Charged Dance Songs for the Desperate, den 12. juli 2004. Den 5-sporede EP blev mødt med positive anmeldelser, som ofte sammenlignede Gay for Johnny Depp med andre hardcore bands, The Blood Brothers og The Locust.
Bandet indspillede deres anden EP, Blood: The Natural Lubricant (An Apocalyptic Adventure Beyond Sodom and Gomorrah), i sommeren 2005, og udgav den den 19. september 2005 på det britiske label Captains Of Industry. Den blev støttet af en lille turné i Storbritannien. Pladen skaffede Gay for Johnny Depp en masse fans, både på grund af de usædvanlige sangtitler og på grund af selve musikken.
Gay for Johnny Depp spillede deres første koncert i Storbritannien nogensinde den 14. september 2005 i Exeter som support for Million Dead. Under showet blev frontmand Marty Leopard slået af et vredt publikum og måtte på hospitalet for at få 5 sting i ansigtet.
Den 9. juni 2006 spillede Gay for Johnny Depp på Download Festival i Donington Park, Storbritannien. Samme år blev deres sang Sex In Your Mouth udgivet på Kerrang! kompilationsalbummet New Breed.
Bandets første fuldlængdealbum, The Politics of Cruelty, blev udgivet den 5. november 2007; det var et sjældent eksempel på et hardcore band, der fik positive anmeldelser i publikationer som NME, Q, The Guardian og Uncut samt i tungere rockpublikationer som Rock Sound. En række numre blev også sendt på BBC Radio 1.
I stedet for at indeholde det sædvanlige biografiske materiale indeholdt de forudgående eksemplarer af albummet, der blev sendt til medierne, et meget eksplicit pornografisk fanbrev til skuespilleren Johnny Depp, som angiveligt var skrevet af en person, der blot var kendt som “Brad”. Denne fremgangsmåde var i overensstemmelse med bandets tidligere reklamemateriale, som har indeholdt flasker med amylnitrit, kirurgiske gummihandsker, kondomer, eksplicitte homoseksuelle fotografier og yderligere eksplicitte breve fra “Brad”.
Bandets debutalbum var på NME’s Top 10-liste i november 2007. Samme måned blev sanger Marty inviteret til at deltage i NME’s årlige Pub Golf-feature. Højdepunkter fra aftenen er efterfølgende dukket op på internettet.
Gay For Johnny Depp turnerede i Storbritannien i januar og februar 2008 og i april 2008 kun iført sokker, der dækker deres kønsdele.
De turnerede igen i Storbritannien mellem 13. november og 4. december 2009.
Bandets andet studiealbum What Doesn’t Kill You, Eventually Kills You blev udgivet den 14. februar 2011.
Den 31. oktober 2011 udsendte de en YouTube-video og en e-mail til deres mailingliste, hvori de annoncerede, at de gik hver til sit.
Deres anden EP, Blood: The Natural Lubricant (An Apocalyptic Adventure Beyond Sodom and Gomorrah) blev genudgivet i september 2012, denne gang på vinyl, begrænset til 300 eksemplarer gennem det uafhængige britiske label Moshtache Records.