Les Flics se forment en 1979 pour avancer sur la voie tracée par Public Image Ltd. ou Wire.
Les premiers membres (Christian Rosset, Bruno Lefaivre et Lilian Picard) se rencontrent au lycée Jeanne D’Arc, vivier rouennais d’artistes en herbe.
Le groupe fréquente le légendaire magasin Mélodie Massacre où ils font la connaissance de Philippe Brossard alors étudiant à l'école des Beaux-Arts. Il remplace Lilian au sein des Flics lorsque celui-ci arrête la musique. Hédi Bouachour en provenance du Havre est recruté pour assurer le chant et l’écriture des textes en 1984.
Le quatuor ainsi formé hésite entre quelques appellations pour se fixer sur Tupelo Soul, en référence aux frères Presley et à un morceau de John Lee Hooker repris par Nick Cave and the Bad Seeds.
Dès les premiers concerts des Flics, le groupe se forge une réputation grâce à leur fureur scénique et leurs compositions aussi brutes que ciselées. Ils partagent des scènes avec les Dogs, The Fall, Virgin Prunes, Danielle Dax, Certain General, Minimal Compact, Moe Tucker, 999 et Damo Suzuki... entre autres. Cette première mouture du groupe dont différents membres sont impliqués dans des projets parallèles (Dogs, Tony Truant, Louise Féron, Les Rythmeurs, Les Gloires Locales...) se dissout à la fin des années 90.
Tupelo Soul se reforme en 2008 avec Nicolas Legrand (Roll Mops, Pleum, Vomir) à la basse et Thibault Aspe (2/3 de Sextet, Yplon) au chant et à la guitare.