Gay for Johnny Depp bildades 2004 av före detta medlemmar från post-hardcorebanden Garrison och Instruction och släppte sin första skivinspelning, Erotically Charged Dance Songs for the Desperate, den 12 juli 2004. Den femspåriga EP:n möttes av positiva recensioner som ofta jämförde Gay for Johnny Depp med andra hardcoreband, The Blood Brothers och The Locust.
Bandet spelade in sin andra EP, Blood: The Natural Lubricant (An Apocalyptic Adventure Beyond Sodom and Gomorrah) under sommaren 2005 och släppte den den 19 september 2005 på det brittiska skivbolaget Captains Of Industry. Detta stöddes av en liten turné i Storbritannien. Skivan fick Gay for Johnny Depp många fans, på grund av de ovanliga låttitlarna lika mycket som själva musiken.
Gay for Johnny Depp spelade sin första spelning någonsin i Storbritannien den 14 september 2005 i Exeter som förband till Million Dead. Under spelningen blev frontmannen Marty Leopard slagen av en arg publikmedlem och fick åka till sjukhuset för att få fem stygn i ansiktet.
Den 9 juni 2006 spelade Gay for Johnny Depp på Download Festival i Donington Park, Storbritannien. Samma år släpptes deras låt Sex In Your Mouth på Kerrang!-samlingsalbumet New Breed.
Bandets första fullängdsalbum, The Politics of Cruelty, släpptes den 5 november 2007; det var ett sällsynt exempel på ett hardcoreband som fick positiva recensioner i publikationer som NME, Q, The Guardian och Uncut samt i tyngre rockpublikationer som Rock Sound. Ett antal låtar sändes också på BBC Radio 1.
Istället för att innehålla det vanliga biografiska materialet innehöll förhandsexemplar av albumet som skickades till media ett mycket explicit pornografiskt fanbrev till skådespelaren Johnny Depp, som påstods vara skrivet av en person som bara var känd som ”Brad”. Detta tillvägagångssätt var i linje med bandets tidigare reklammaterial, som har innehållit flaskor med amylnitrit, kirurgiska gummihandskar, kondomer, explicita homosexuella fotografier och ytterligare explicita brev från ”Brad”.
Bandets debutalbum var med på NME:s topp 10-lista under hela november 2007. Samma månad blev sångaren Marty inbjuden att delta i NME:s årliga Pub Golf-inslag. Höjdpunkter från kvällen har senare dykt upp på internet.
Gay For Johnny Depp turnerade i Storbritannien i januari och februari 2008 och i april 2008 utan något annat än strumpor som täckte deras privata delar.
De turnerade i Storbritannien igen mellan den 13 november och 4 december 2009.
Bandets andra studioalbum What Doesn’t Kill You, Eventually Kills You släpptes den 14 februari 2011.
Den 31 oktober 2011 släppte de en YouTube-video och ett mejl till sin mailinglista där de meddelade att de gick skilda vägar.
Den andra EP:n, Blood: The Natural Lubricant (An Apocalyptic Adventure Beyond Sodom and Gomorrah) gavs ut på nytt i september 2012, denna gång på vinyl begränsad till 300 exemplar genom det oberoende brittiska skivbolaget Moshtache Records.