That same year, two new albums came out. Originally, both albums were planned to be released at the same time, but however, the record company have decided to release them one month from another; they thought both albums would sell more if they were not released simultaneously. The first to be released was Mercyful Fate's "Into The Unknown", on August 20th 1996. This album was much more progressive than any other album Mercyful Fate ever released. The Japanese pressing contained also "The Ripper" as a bonus track. For this album, the band recorded all the instruments, except the vocals, 'live' at the same time. During the sessions, the band made a song that unfortunately have not been included on the album: "The Storm", which, according to Hank, would be in the vein of Judas Priest.

The first track on the album was not a song in the true sense of the term, but more of an intro, as the band wanted to have a new intro for their upcoming concerts instead of always keeping on using the "The Oath" intro part; that was basically the idea for the song "Lucifer". Another interesting fact concerning the songs is that for a second time, the band made a sequel to a song, as "Kutulu (The Mad Arab Part Two)" is the continuation of "The Mad Arab" that was previously released two years earlier. That was something they decided already when they did the "Time" album as King couldn't get all the story to fit into this one song, so they decided to write it into two separate songs. It was also a challenge to create some Arabian kind of style in there with the middle section. The Arabian sound with guitar had some special effects on it; Hank had an old pedal from the 70's, and then they used a bass with some stuff on it, with distortion and added to it a tambourine. That was pretty simple, only two guitars there playing two different roles with bass, tambourine, and King was doing some stuff in there as well. Then it breaks into this very up-tempo Heavy Metal which ends the whole song and is also kind of progressive in a way with a lot of complicated musical sequences going up to this riff at the end of the song.

A promo video have been made for the "The Uninvited Guest" in the following summer. This video was shot in an old church in Denmark built in 1153, and we can even see the caretaker of the church in the video. The band was able to use the church simply by bribing two church employees, an inn-keeper and a custodian, as two bottles of cognac were all that was needed. Band manager Olé Bang and the video's producer arranged the church, so the inn-keeper, completely unfamiliar with Mercyful Fate, had never seen King until the day of filming. When King arrived in full make-up, he hid his face to the inn-keeper and warned him not to be scared when he would look up. King recalls the man's reaction, as he nearly got a heart attack.

A short while later, during the tour following that album, Michael Denner left the band to celebrate his second son's birth. Michael asked the band to bring Mike Wead in the band to replace him through this time. He thought Mike was not only a good musician, but that he also had the same kind of playing that Michael had, so he replaced him temporarily for the remaining dates of the tour. Nice fact: Mike Wead and Snowy Shaw were together in the same band once again two years before in Memento Mori.

Then came out the new King Diamond album, "The Graveyard" on the following September 20th, which has been recorded earlier that year from March until May. To introduce his fans this new album, King changed his make-up quite drastically; as the previous make-up, which he used since the "Conspiracy" album, represented too much work and time to put on, this new one consisted only of black make-up around the eyes and mouth, reminding well the first make-up used with Mercyful Fate, with the exception of the inverted cross in the face and less black under the lips.

All the King Diamond albums have stories that touch very deep on the human mind and human nature, but this time, the story touched on a subject that is often taboo: incest. This subject seemed to touched so much King that not only he thought many times about giving up the story, but King often gave the impression that he was going insane on the album, just like in the ending part of the song "I Am"; King was supposed to repeat only three times the word "Die!", but King went too deep into the story that when he did it in the studio, he went so crazy that he started yelling "Die, Die, Die, Die..." like a madman, completely spontaneous. Nobody spoke a word, it was clear this take had to be the right one! He poured out every emotion inside and totally flipped out. He just went completely off as he almost puked afterwards. He was to a point where he just totally emptied himself of everything. What is on the album is a first take. On this album also, there was the song "Daddy" which, until then, took King the less time to write; actually, that song took only 20 minutes and the lyrics were done.

In 1997, Michael Denner told the band he would not come back in the band so Mike Wead stayed permanently in Mercyful Fate. Michael needed to stay with his family, and also, he owns a second-hand record store, mostly vinyl, called Beat-Bop Records, and he needed some time to run his store properly. During this year, both bands were touring together, as Mercyful Fate opened for King Diamond. Even though it was something King wanted to do since a while, it was something very though for him as he had to sing for nearly 3 hours each night; each band played about 75 minutes, and there was a 45 minutes break between both bands, to give King some time to change his make-up and get some rest. He had to take extra care of his voice. Meanwhile, drummer Darrin Anthony has been victim of a car accident. This accident would eventually force him to leave the King Diamond band as he wasn't able to drum anymore. He have been replaced by another American drummer: John Luke Hébert, who came from Louisianna. King thought it would be better to have John on drums, because even though Darrin was not a bad drummer, King thought that he never really was at the level that the band should have had for the albums they recorded; he just didn't really do much with the music. That year, even though there were no new albums of Mercyful Fate or King Diamond that have been released, King had a lot of job to do for recording the albums of his both bands that had to be released during the following year.

Like if it was not enough, King had to work on the remastered versions that Roadrunner planned to release later that year. It all started a few days before going into the studio recording the new King Diamond album. King was with Andy when Monte Conner from Roadrunner called up and told them about the upcoming remasters project. King thought it was a good idea, but the timing was not really perfect since the band was already very busy with the recording sessions at this time. The first CD versions were made in the early days of the CD, and in those days it was almost 6 decibels lower output than what they could do in 1997. They couldn't really do a remix, but could do a remaster on it, which helps a lot as they could change tiny little bits and pieces. But then, all of a sudden, in the middle of the procedure, they were given new shorter deadlines. There were some things that they just couldn't get done in that time, which would have made it even better, but considering the time they had, King thinks it turned out really good; they sound better and they look better. However, King wasn't very pleased with the final result of "Don't Break The Oath". They did a very good job when you take into consideration how much time was actually given to that project. The band was very involved with it, with some of the bonus tracks and stuff that only King had on tape that Roadrunner had never heard.

As King and Andy were listening to a lot of different tapes, they suddenly got their hands on the "Abigail" sessions. None of them seemed to remember what it was. These outtakes from the "Abigail" album were actually stuff that whenever King had done vocals in the studio, the band would do a quick mix of that song, and then King could take it home with him and listen to it and see if he wanted to change any of the vocals, or whatever, the next day. So those were quick mixes of that, and we can actually notice that there are vocals parts that are on those versions that have never made it to the album. Then for those two songs from "Them", King has the entire album recorded in a rehearsal session, except for the horror pieces, of course, which were done in the studio. But all the real songs from "Them", he has those in that same quality. And the crazy thing about that, is that it featured guitars by Andy on one side and King on the other, since Pete wasn't there yet at the time the band recorded these demos. And later on, before going into the studio, Timi left the band but had stayed in the studio teaching his bass lines to Hal, so Timi plays on these demo versions as the same bass lines are played by Hal on the album. The "Conspiracy" album also came with two bonus tracks: a live mix of "Cremation" that was meant to be played on tape during the band's live performance, but has never been used, and also the original mix of "At The Graves", which has very low guitars but very loud vocals, which demonstrates how you can really change the atmosphere of a song just by varying the levels of a vocal or a background instrument.

This stuff all went from tapes which King has in his basement, which is actually a box of tapes containing lots of outtakes and unfinished material; riffs, choruses and verses. Sometimes, when making a new album, he gives those tapes a listen to help him create new music tracks. It happened, among others, for some songs on "The Spider's Lullabye" and "The Graveyard", which some riffs of these songs were originally created around 1987-1988, but haven't been used at the time of their creation though.

The remastered versions were finally released by Roadrunner in November 1997, and they all contained some new pictures as well as liner notes written by Don Kaye, a renowned metal critic and writer who also worked with magazines such as Circus, Hit Parader, Guitar World, Kerrang!, Metal Edge, Metal Maniacs and many others since the late 80's. The first pressing of those remastered versions were on gold discs, which are rarer than the usual silver discs that later been pressed. For 3 of the remastered versions ("Abigail", "The Beginning" and "In Concert 1987 - Abigail"), the cover sleeves have also been modified. Also, 6 of the 9 remastered albums contained bonus tracks: "Don't Break The Oath" ("Death Kiss [demo]"), "Fatal Portrait" ("No Presents For Christmas", "The Lake"), "Abigail" ("Shrine", "A Mansion In Darkness [rough mix]", "The Family Ghost [rough mix]", "The Possession [rough mix]"), "The Beginning" ("Black Funeral [1982 version off the Metallic Storm compilation]"), "Them" ("Phone Call", "The Invisible Guests [rehearsal]", "Bye Bye Missy [rehearsal]") and "Conspiracy" ("At The Graves [alternate mix]", "Cremation [live show mix]"). Only the albums "Melissa", "The Eye" and "In Concert 1987 - Abigail" didn't contained any bonus tracks. Also, of all the albums officially released by Roadrunner, 3 albums have not been remastered: "The Dark Sides", "Return Of The Vampire" and "A Dangerous Meeting".