A 2004-ben a Garrison és az Instruction nevű post-hardcore zenekarok volt tagjaiból alakult Gay for Johnny Depp 2004. július 12-én adta ki első lemezfelvételét Erotically Charged Dance Songs for the Desperate címmel. Az 5 számot tartalmazó EP pozitív kritikákat kapott, amelyek gyakran hasonlították a Gay for Johnny Depp-et a The Blood Brothers és a The Locust hardcore zenekarokhoz.
A zenekar második EP-jüket, a Blood: The Natural Lubricant (An Apocalyptic Adventure Beyond Sodom and Gomorrah) című albumát 2005 nyarán, és 2005. szeptember 19-én adták ki a brit Captains Of Industry kiadónál. Ezt egy kisebb turnéval támogatták az Egyesült Királyságban. A lemez sok rajongót szerzett a Gay for Johnny Deppnek, a szokatlan dalcímek miatt éppúgy, mint maga a zene miatt.
A Gay for Johnny Depp 2005. szeptember 14-én játszotta első brit koncertjét Exeterben, a Million Dead előzenekaraként. A koncert alatt a frontembert, Marty Leopardot megütötte a közönség egy feldühödött tagja, és kórházba kellett mennie, hogy 5 öltéssel összevarrják az arcát.
2006. június 9-én a Gay for Johnny Depp a Download fesztiválon játszott az Egyesült Királyságban, a Donington Parkban. Ugyanebben az évben a Sex In Your Mouth című daluk megjelent a Kerrang! válogatásalbumán, a New Breed-en.
A zenekar első nagylemeze, a The Politics of Cruelty 2007. november 5-én jelent meg; ritka példa volt arra, hogy egy hardcore zenekar pozitív kritikákat kapott olyan kiadványokban, mint az NME, Q, The Guardian és Uncut, valamint olyan keményebb rock kiadványokban, mint a Rock Sound. Néhány számot a BBC Radio 1 rádióban is sugároztak.
Ahelyett, hogy a szokásos életrajzi anyagot tartalmazta volna, a médiának küldött album előzetes példányai egy rendkívül explicit pornográf rajongói levelet tartalmaztak Johnny Depp színésznek, amelyet állítólag egy egyszerűen “Brad” néven ismert személy írt. Ez a megközelítés összhangban volt a zenekar korábbi promóciós anyagaival, amelyek amil-nitrites üvegeket, sebészeti gumikesztyűket, óvszereket, explicit homoszexuális fotókat és további explicit leveleket tartalmaztak “Brad”-től.
A zenekar debütáló albuma 2007 novemberében végig az NME Top 10-es listáján szerepelt. Ugyanebben a hónapban az énekes Marty-t meghívták, hogy vegyen részt az NME éves Pub Golf funkciójában. Az est fénypontjai később megjelentek az interneten.
A Gay For Johnny Depp 2008 januárjában és februárjában, valamint 2008 áprilisában úgy turnézott az Egyesült Királyságban, hogy csak zoknit viseltek, ami eltakarta a nemi szervüket.
2009. november 13. és december 4. között ismét turnéztak az Egyesült Királyságban.
A zenekar második stúdióalbuma What Doesn’t Kill You, Eventually Kills You 2011. február 14-én jelent meg.
2011. október 31-én kiadtak egy YouTube videót és egy e-mailt a levelezőlistájuknak, amelyben bejelentették, hogy külön utakon folytatják.
A második EP-jük, a Blood: The Natural Lubricant (An Apocalyptic Adventure Beyond Sodom and Gomorrah) 2012 szeptemberében jelent meg újra, ezúttal 300 példányra limitált bakeliten a független brit Moshtache Records gondozásában.