The band formed at the end of the 1990s in Birmingham and began playing their own take on the vitriolic Iron Monkey / Eyehategod sludge sound. The band became noted for their offensive, yet intellectual lyrics and incredibly heavy, dirty, downtuned sound.

In 2001, Mistress released two demos, entitled Fuck Off and Lord Worm, which got them signed to the underground Rage Of Achilles extreme music label. Their first full-length album for the record label was the self-titled Mistress in April 2002, which received broadly good reviews from extreme music publications. The follow-up to this, October 2003's Mistress II: The Chronovisor, helped to more firmly establish them as a metal band, along with their growing live reputation.

The band's ability to create filthy sonic rage ensured that they were soon picked up by the much larger Nottigham-based Earache Records, who issued Mistress' third full-length album In Disgust We Trust in June 2005. In the same year, Earache also re-issued the band's first two albums. After being dropped from the Earache roster during 2006, the band were signed to Mick Kenney and Shane Embury's new record label, FETO Records.

On 23 April 2007, they released their fourth studio album through FETO Records, entitled The Glory Bitches Of Doghead which has dropped the sludge sound in favour of enhancing the grind elements. The album also has an ambient track running throughout (consisting of various noises, including what seems to be rain) created by Misery, which can be heard distinctly between songs, adding depth to the vicious music being played.

Mistress appeared on the Christmas special of Never Mind The Buzzcocks, performing Christmas carols in sludge metal.

Mistress announced their demise on 4 March 2008.