Yhtye muodostettiin post-hardcore-yhtyeiden Garrison ja Instruction entisistä jäsenistä vuonna 2004, ja Gay for Johnny Depp julkaisi ensimmäisen levynsä Erotically Charged Dance Songs for the Desperate 12. heinäkuuta 2004. Viisiraitainen EP sai positiivisia arvosteluja, joissa Gay for Johnny Deppiä verrattiin usein muihin hardcore-yhtyeisiin The Blood Brothers ja The Locust.
Yhtye levytti toisen EP:nsä, Blood: The Natural Lubricant (An Apocalyptic Adventure Beyond Sodom and Gomorrah) kesällä 2005 ja julkaisi sen 19. syyskuuta 2005 brittiläisellä Captains Of Industry -levymerkillä. Tätä tuettiin pienellä kiertueella Yhdistyneessä kuningaskunnassa. Levy sai Gay for Johnny Deppille paljon faneja, mikä johtui niin epätavallisista kappaleiden nimistä kuin itse musiikista.
Gay for Johnny Depp soitti ensimmäisen keikkansa Isossa-Britanniassa 14. syyskuuta 2005 Exeterissä Million Deadin tukena. Keikan aikana eräs vihainen yleisön jäsen löi keulamies Marty Leopardia ja joutui sairaalaan saamaan viisi tikkiä kasvoihinsa.
9. kesäkuuta 2006 Gay for Johnny Depp esiintyi Download-festivaalilla Donington Parkissa, Iso-Britanniassa. Samana vuonna heidän kappaleensa Sex In Your Mouth julkaistiin Kerrang! kokoelmalevyllä New Breed.
Yhtyeen ensimmäinen kokopitkä albumi The Politics of Cruelty julkaistiin 5. marraskuuta 2007; se oli harvinainen esimerkki hardcore-yhtyeestä, joka sai positiivisia arvosteluja NME:n, Q:n, The Guardianin ja Uncutin kaltaisissa julkaisuissa sekä rockin raskaammissa rock-julkaisuissa kuten Rock Soundissa. Useita kappaleita esitettiin myös BBC Radio 1:ssä.
Tavanomaisen elämäkerrallisen materiaalin sijasta medialle lähetetyt ennakkokopiot albumista sisälsivät näyttelijä Johnny Deppille osoitetun erittäin eksplisiittisen pornografisen fanikirjeen, jonka kirjoittajaksi väitettiin henkilöä, joka tunnettiin yksinkertaisesti nimellä ”Brad”. Tämä lähestymistapa vastasi yhtyeen aiempaa promootiomateriaalia, joka on sisältänyt amyylinitriittipulloja, kirurgisia kumihanskoja, kondomeja, eksplisiittisiä homoseksuaalisia valokuvia ja lisää eksplisiittisiä kirjeitä ”Bradilta”.
Yhtyeen debyyttialbumi oli koko marraskuun 2007 ajan NME:n Top 10 -listalla. Samassa kuussa laulaja Marty kutsuttiin osallistumaan NME:n vuotuiseen Pub Golf -tapahtumaan. Illan kohokohdat ovat sittemmin ilmestyneet internetiin.
Gay For Johnny Depp kiersi Iso-Britanniassa tammi- ja helmikuussa 2008 sekä huhtikuussa 2008 pukeutuneena vain sukat jalassaan peittäen heidän sukupuolielimensä.
Yhtye kiersi jälleen Iso-Britanniassa 13.11.-4.12.2009.
Yhtyeen toinen studioalbumi What Doesn’t Kill You, Eventually Kills You julkaistiin 14.2.2011.
31.10.2011 he julkaisivat YouTube-videon ja sähköpostiviestin sähköpostilistalleen ilmoittaen, että heidän tiensä eroavat.
Yhtyeen toinen EP, Blood: The Natural Lubricant (An Apocalyptic Adventure Beyond Sodom and Gomorrah) julkaistiin uudelleen syyskuussa 2012, tällä kertaa 300 kappaleeseen rajoitetulla vinyylillä riippumattoman brittiläisen Moshtache Recordsin kautta.