On September 8th 2003, Roadrunner Records released a serie of "Two From The Vault" double-albums for 9 bands, and among others such as Annihilator, Suffocation and Obituary, there was also King Diamond and Mercyful Fate. The one from King Diamond was a 2-discs set containing his first two albums: "Fatal Portrait" and "Abigail". The one from Mercyful Fate, still a 2-discs set, was comprised of "Melissa" and "The Beginning". All albums were the same remastered versions that were originally released in 1997, with the same bonus tracks on each disc.

Two weeks later, on September 12th, Roadrunner Records released a serie of "Best Of" albums, henceforth dubbed "The Roots Of Roadrunner". These works were made by Monte Conner from Roadrunner Records which have previously worked on the remastered versions of the early Mercyful Fate and King Diamond albums in 1997. "The Best Of Mercyful Fate" featured 14 classics, and contained liner notes from Mark Hunter, the singer of the hardcore band Chimaira. "The Best Of King Diamond", on its side, contained 15 songs, and this time, the liner notes were written by former Megadeth bassist Dave Ellefson.

On the following October 7th, Purging Talon released a DVD called "Church of Satan: Interview Archive". This video documentary contained the interview with King taken from the "Geraldo" special from 1988. Even though the main feature presentation is a little under an hour, King's interview is fairly short, about a minute only. There is a little picture of King on the cover of the DVD taken from this interview as we could see him with his "Them"-era make-up.

On October 20th 2003, the new studio album of King Diamond was officially released, "The Puppet Master". However, in some countries, the release date have been pushed back until November 18th, and in some places in Canada, it has been released on December 23rd, which led to numerous complaints as the American tour was already over by that time. Apparently, a distribution problem would have been at the root of this. On his side, King found it would be weird playing some shows with three new songs from the album before it gets released, as he never done that before.

King originally had the main idea for "The Puppet Master" album while he was touring with Mercyful Fate supporting "9". During that tour, they went to Budapest, Hungary, on June 3rd 1999, and they have seen this big place called the National Puppet Theatre, which looked like a 1500 capacity theatre. King couldn’t imagine what kind of puppets they would have in there if there was like 1500 people; they must be huge. There were all these puppet shops along the same street that he saw which looked so creepy when you looked into them. They had puppets of all sizes, and some were sitting on chairs, other were hanging on walls, and all those things gave him ideas which he wrote down, and then they were put away for a long time. He has a box with all kinds of things he have written down for possible later use, and now was the right time for those ideas to be used. With this album, King wanted to put more horror than on his latest albums, as he heard some people complaining that his latter albums were not as dark as his earlier works. King considered it was his best work yet, and the most gruesome story he ever written. This is pure and utter tragedy for the main characters, and at the opposite of any of King's other stories, the evil ones wins at the end. The first song of the album, which is actually the introduction of the album, was originally called "The Cellar", but as the process of the album grew on, it was retitled to "Midnight". At some point, an instrumental song was planned to be included, however it didn't made it. Even though Matt was the drummer, he contributed a guitar riff for a song on the album: "No More Me". The ballad "So Sad" is very emotive for King as 90% of that song is about someone who was very special for him and who deceased shortly before: Ghost, a white male cat that King had from an animal shelter. The song is actually dedicated to his memory, as King always been very close to his cats, and losing Ghost was something that saddenned him a lot, and every time King hears the first note of the song, he finds it heavy duty. The 10% remaining of "So Sad" has been changed only to fit the story.

As the story takes place around Christmas time, the classic holiday theme "The Little Drummer Boy" was used on the song "Christmas". For the second time, King builded something around the Christmas theme, which he considers being a very cozy tradition, even though he doesn't commit to a particular organized religion. For him, it’s not associated with any child that was born magically by a virgin but just some old heathen tradition. Looking forward as a kid and almost getting sick because of the wait for the presents, he always loved that time of year. Still today, with all the shops decorated and stuff, he finds it absolutely beautiful. In addition, his all-time favourite meal is the national Danish Christmas dinner, which consists of roast pork, goose or beef while the dessert consists of rice pudding (Julgrot) which has a lucky almond hidden in it. King also loves ice cream and coffee.

For the first time, King asked a female singer, Livia Zita, to perform some parts on the album. The way they went it touch was quite odd, actually. When King finished "Abigail II", Livia was doing an interview for Metal Hammer Hungary regarding that album. Born in Budapest, Hungary, just like in "The Puppet Master" story, she was in the USA studying in Michigan at this time, so she called King from there to ask about "Abigail II". They talked for a while and did the interview and then she mentioned to him that she was also a singer. In fact, she had a little musical training too. A lot of people have said that to him, but it never went further, but that one time, she said she had a demo that she felt pretty proud of, and that it would be an honour to hear King's opinion about it, and so she sent it. The song was a Nightwish ballad, and there was so much emotion that King was completely amazed. Then King started to write the story for "The Puppet Master", and the further he got into it, King thought that this story had the potential to become really theatrical, more than ever before. The problem was that the female character was playing quite a big role in the story, and if King would have sang female parts, it would have much less impact than a real female singer. Also, King liked the idea of having a guest female singer on the album, as it would be something fresh without necessarry changing the King Diamond style. Then King played Livia's demo to the other guys in the band, as well to the staff from the record company, just to get more opinions regarding that, and they all agreed it would be a good idea to have her on the album. Then King talked to her and eventually she came over and recorded and it turned out so good. It also was so well received by the fans; they all loved this new element that came in because it made everything so much more theatrical, and in addition, King found that the tonality of her voice fits his extremely well and that she had a lot of goth and feeling. Livia then also followed the band on tour, just like the actress and dancer Jody Cachia.

Another thing that was different with this album was the way the recording process went, as the main tracks were all recorded in King's home, and they went to studio only afterward. The band had to act differently this time because of the budget cuts from all the downloading on Internet of "Abigail II", which represents a loss of about 30% of the normal King Diamond sales for Metal Blade Records. That loss of sales not only affected the band because there was no funds for a tour supporting the last album, but it also affected the budget allowed for the next album because there was no way the band could record the entire album in the studio. However, it totally turned out better than they thought. So Andy recorded the keyboards at his Los Angered Studios in Sweden, and actually took his best recording equipment from Gothenburg, broke it down, and filled two flight cases and shipped them to King's home in Dallas and they turned his living room in a studio. His speakers were the same as the ones Andy used in his studio, and in Nomad Studios also. So the listening factor was unchanged from where they were at all times, and this was all done on the top notch recording equipment. All the rhythm guitars, bass and keyboard parts were done at King's house; the drums and vocals were done at Nomad Studios. At that time, Andy had prior commitments to another band project back home and had to pack and ship all this stuff back to Sweden to do his job, so he did his solos back there as well. Then they shipped all that stuff back to mix the entire album at King's house. That gave them more time in Nomad Studios, so the clock wasn't ticking when they wanted to put the reverb here, or place backing vocals wherever they wanted; they were not pressed for time so this time they didn't feel that rushed. They were more relaxed and it was more fun. Hal and Andy were staying in guest rooms in King's house, and they were still working 12 hours a day, but in a whole different atmosphere. By being smart and exploring different options, they came up with a product that King thinks is better than anything he ever did, and this is a very crisp sounding album; they sat in a room of carpet and chairs, just like fans are gonna hear it in their environment, that is how they mixed it at his house so they knew how it would sound on average at someones' house when they play it.

The album also included a 30-minute extra DVD, showing King telling the story of "The Puppet Master" in full make-up. The filming took place at King's house; they just set up part of the dining area, took little things King have displayed in his home and put a black cloth on the table and began from there. We can even see his famous Necronomicon on the table. Even though it was a low budget thing, King thinks it was a very good companion to the story, as it was different for the fans to see him sit down and tell a version of the story that was just straight from his memory, without any notes or anything, without even any rehearsal. They filmed it with just one camera, but King told the story three times, so they shot it from one camera angle, then another one and another one and edited that together. When King finally got the accepted version by 11:00 a saturday morning, it was sunshine outside and he sat and watched it on his DVD in his living room in Phoenix and he got sucked in then. He never heard any bad things about it, anyway it's just a bonus when buying the album. The idea of the DVD actually came from Metal Blade Records president Brian Slagel. When he went to King's house for a business meeting, King told him the story of the album, just like in the DVD, right off his memory. It was another bright sunny day, and Brian thought it would be a good idea to record this as a bonus track at the end of the disc, or better yet, to shoot it on DVD.

The tour that followed was mainly devoted for both "Puppet Master" and "Abigail II" stories, since no tour happened in support to "Abigail II". The American leg of the tour began on October 18th in Los Angeles and ended in San Antonio, Texas, on November 22nd. The European part, scheduled after the Christmas break, has then been put on the ice for a while. The time passed by, the more rumours grew that there would be no European tour supporting "The Puppet Master".

At some point, there were rumors that Mercyful Fate would have ceased to exist. In fact, King was so busy with his own band that there was not really time left for Mercyful Fate to record something new. Even though all of its members have other bands to play in, it always have been clear to everybody that Mercyful Fate would always remain their main priority whatever else they were doing: King and Mike were working on King Diamond, Sharlee was still working with Witchery and Arch Enemy, Hank was still composing and writing all sorts of music, not just heavy metal, in addition of his new band Force Of Evil, and Bjarne was playing with some local acts in Denmark as well as with Force Of Evil too. However, even though Mercyful Fate is not over yet, only time will tell what will happen exactly. Maybe the band will return with the members that were on the last album, maybe it will feature new members, or even the original line-up, so as of today, anything is possible. As a proof that the band was still alive and well, a Mercyful Fate DVD was scheduled to be released for Christmas 2003. This DVD would feature a behind-the-scenes kind of thing with some old concert footage that probably no one has ever seen. However, the release date has then been postponed to a later date, and now it is still to come.

After the American Tour to promote "The Puppet Master", the entire King Diamond band, minus King himself, joined the Swedish King Diamond tribute act Kung Diamant for a couple of tuned during their set, which was held on December 13th at Pianobaren in Trollhättan, Sweden. Interesting detail: the guitarist of Kung Diamant, Mark U Black, used to be related to King Diamond in some ways, as he previously was in a band called "Ton Of Bricks" along with vocalist Yonas Af Dahlstrøm, formerly from Illwill, a side project featuring Andy LaRocque, Sharlee D'Angelo and Snowy Shaw. Mark was also about to join the band Dream Evil, which he joined sometime in 2004, another band featuring Snowy at that time.

In early 2004, Roadrunner Records released more titles of its serie called "Two From The Vault", which included a double release of King Diamond comprised of "Them" and "Conspiracy", and one of Mercyful Fate comprised of "Don't Break The Oath" and "Return Of The Vampire". The first one was released on January 27th, and the latter one came out during the following summer, precisely on July 13th.

On February 10th, the long-awaited Probot project has been released. Created by former Nirvana drummer and current Foo Fighters frontman, Dave Grohl, this project has been released both on CD and limited edition 2-LP set.

The more weeks passed by, the more rumours grew that there would be no European tour supporting “The Puppet Master”. Some rumours even stated that King's health was very poor, which was denied by King himself next August 3rd in a statement posted on his official website. In that statement, King admitted that there would be no tour in Europe that year for political and immigration reasons. In fact, the only reason was that King's immigration and naturalization process with the American government was taking longer than expected, and this procedure prevented him from leaving the country. King have been applying for naturalization in March 2003 and his first test date was in the following month of November, while he was on tour supporting the release of "The Puppet Master". He only got about two weeks notice for the test, and so he already was on tour when he got the notice, so he told his lawyer that he had to reschedule it and he expected it would be rescheduled for December or something because they were finished touring later in November. You can only reschedule once, and after the second time, you have to start all over again, which meant that it was out of the question for him. He expected it would go about two months for another test, but that was not the case. There's nothing he could do, just have to abide by the law, awaiting a new test. The reason for this taking so long is probably because of all the extra precautions and checks the American government had to take in those times of terrorism. However, during this time, King, as always, didn't wasted any time as he already began planning the next album. The songwriting was planned to start a couple of weeks later, in order to tentatively record the music before Christmas, record the vocals in january and release the album during 2005. That time, King promised he would pay a visit to his European fans. In the meantime, King got married for the second time, six years after his divorce with Deborrah. His bride was Livia Zita, the yound female singer that appeared on "The Puppet Master" album, as well as on the tour that followed.