Rednex var til at starte med tænkt på af de svenske producere Janne Ericsson, Örjan "Öban" Öberg, and Pat Reiniz,[1]
der besluttede sig for at mixe amerikansk folkemusik med eurodance. Navnet "Rednex" blev valgt som en bevidste stavefejl af ordet "Redneck".[kilde mangler]
Det Rednex line-up der startede gruppen, som det ses i videoen til "Cotton Eye Joe", bestod af figurerne Mary Joe (aka Karin Annika Ljungberg, der sang det meste af den kvindelige vokal på Sex & Violins), Ken Tacky, Bobby Sue, Billy Ray og Mup (aka Pat Reiniz). Kort efter udgivelsen af "Cotton Eye Joe", blev figuren Mup erstattet af BB Stiff.
I 1996 blev den kvindelige forsanger, Mary Joe, fyret, til dels på grund af uoverensstemmelser med de andre gruppemedlemmer,[2] og forsøgte sig herefter med en solokarriere.[3] Resten af bandet tog en pause fra live-optrædender og startede med at arbejde på nyt materiale..[4]
Whippy (aka Mia Löfgren) blev den nye kvindelig vokalist i 1998. I 1999 forlod Ken Tacky gruppen, hvilket reducerede antallet af mandlige kunstnere fra fire til tre.