Debiutancka płyta "Melissa" ukazała się jesienią 1983 roku i okazała się być wielkim sukcesem. W maju 1984 Mercyful Fate wydało drugi album "Don't Break The Oath", po czym ruszyło w pierwszą trasę koncertową po Ameryce, u boku Motorhead. Oba krążki są dzisiaj określane jako klasyki, zarówno gatunku power jak i black metal. Z powodu nieporozumień doszło jednak do rozpadu Mercyful Fate w roku 1985, a jego lider stworzył grupę King Diamond. W 1987 roku w sprzedaży ukazała się kompilacja "The Beginning" zawierająca EP-kę "Nuns..." oraz 5 innych, rzadkich utworów.
Po ośmioletniej przerwie, w roku 1992 głównie za sprawą Hanka Shermanna doszło do reaktywacji Mercyful Fate. Wspólnie z Kingiem niemal w całości odtworzyli pierwotny skład grupy z wyjątkiem perkusisty, którego zastąpił Morten Nielsen. W roku 1993 muzycy nagrali album "In The Shadows", zawierający ponownie nagrany utwór "Return of the Vampire". W sesji udział wziął perkusista Metalliki i wielki fan Mercyful Fate - Lars Ulrich. W kolejnych latach na rynku ukazały się krążki "Time" (1994), "Into the Unknown" (1996) i "Dead Again" (1998). Wszystkie albumy osiągnęły dobre wyniki sprzedaży w USA. W 1999 roku zespół wydał ostatni jak do tej pory longplay "9", charakteryzujący się, podobnie jak jego poprzednik, nieco cięższym brzmieniem. W tym samym roku King rozwiązał grupę, a muzycy rozpoczęli kariery w innych formacjach (m.in. Arch Enemy i Force Of Evil).
W 1997 roku grupa zawitała do Polski (Kraków, Poznań) w ramach specjalnej trasy koncertowej u boku grupy King Diamond. Nigdy wcześniej ani później oba zespoły wspólnie nie koncertowały.
W 2005 roku King stwierdził, że Mercyful Fate wciąż ma kontrakt płytowy i mógłby nagrać kolejny album, lecz jako że Fate nie jest w stanie zarobić na swoje utrzymanie (sic!), grupa mogłaby to zrobić w zasadzie tylko w ramach "hobby".