Les Nashville Pussy sont formés à Athens en Géorgie aux États-Unis, par Blaine Cartwright et sa femme Ruyter Suys. Le nom du groupe fait référence à une phrase que Ted Nugent aurait prononcée durant une tournée dans le Tennessee. Cette phrase est audible sur l'album Double Live Gonzo en introduction de la chanson Wang Dang Sweet Poontang.
Le groupe se démarque très vite de la scène Rock en Géorgie en jouant du Hard Rock et du Heavy Metal mêlés à des sons évoquant le Rock Sudiste. Le groupe commence d'abord par jouer des reprises de ACDC, ZZ Top ou Kiss, ainsi que quelques compositions de Blaine Cartwright. Au couple se greffe la bassiste Corey Parks (qui ne passe pas inaperçue sur scène du haut de ses 1,91m) et le batteur Adam Neal, également batteur d'un précédent groupe de Cartwright. Du fait de son nom et des paroles de ses chansons, le groupe se fait une image scénique très pornographique avec notamment Ruyter et Corey.
Vers 1995, Neal quitte le groupe et est remplacé par Jeremy Thompson. Vers 1998, le groupe entame un cycle de grandes tournées européennes et américaines. À cette époque sort leur premier EP Let Them Eat Pussy avec une pochette volontairement provocatrice, mais qui décrit bien la philosophie du groupe : sex, fun and rock'n'roll. En 1999, le groupe passe à la vitesse supérieure et tourne avec Marilyn Manson, ce qui leur permet de jouer devant des milliers de personnes. Fin 1999, ils tournent même avec leurs idoles Motörhead et Lynyrd Skynyrd. En 2000 sort High As Hell, deuxième album qui rencontre un énorme succès. Après des festivals en compagnie de Slipknot ou Slayer, Corey Parks décide de quitter le groupe pour diverses raisons, dont sa non-implication. Elle est remplacée par Tracy Almazan, batteuse de formation, mais qui se met à la basse ; Tracy Almazan ne reste pas longtemps et est remplacée par Katie Lynn Campbell. En mai 2002 sort le troisième album Say Something Nasty, synonyme de reconnaissance mondiale avec des tournées en tête d'affiche en Europe, au Japon et aux États-Unis. Katie Lynn quitte les Nashville Pussy pour former son propre groupe. Fin 2004, les Nashville Pussy font une pause de quelques mois. Blaine en profite pour trouver une nouvelle bassiste, la ravissante Karen Cuda, qui jouait alors dans un groupe de Punk Rock local. En 2005 sort un nouvel album Get Some. S'ensuivent des tournées en Europe, au Japon et en Amérique du Nord avec notamment Reverend Horton Heat et, en invité pour quelques dates, Lemmy Kilmister. Le best of Dirty Best Of sort ensuite.
Début 2009 sort l'album From Hell to Texas. Dans cet opus, le groupe penche encore plus vers le Rock Sudiste, avec des sonorités proches de celles de ZZ Top par exemple, tout en gardant ce panache et ces riffs assassins à la ACDC. En 2012, Karen Cuda ne participe plus aux prestations scéniques en raison de problèmes de santé et se trouve notamment remplacée par Bonnie Buitrago. Le 19 mars 2013, Karen annonce officiellement sa démission du groupe. En 2014 sort Up The Dosage qui est une demi déception pour les fans, l’album est plus calme et même Country par moment, sur ce coup les Nashville Pussy ont perdu un peu ce qui a fait leur succès : la folie.

Les prestations scéniques scéniques des Américains sont toujours ultra énergiques, les concerts sont de véritables show.