In addition of recording his new album, King recorded some vocals on the title-track of "Necronemesis", the upcoming album of the Chicago-based death metal band Usurper in March. The whole thing with Usurper began as they were booked in the same studio that King Diamond was recording his new album. However, King Diamond was going over time, and the owner said that there was this other band waiting for the studio to record their album. But King wasn't interested in leaving the studio as his job was not finished yet, no way in hell, because if they would throw him out, he would never be coming back as he would never going to get that same feeling again. So King asked the owner to call them, and asking them if they would agree to change their plans if they wanted to stay in that same studio, maybe he could do some guest vocals on their album if they wanted to. Usurper gladly accepted what King was offering them, so King came in one day for two hours for them and did one verse and a chorus. That was really strange for King to do, because it wasn't even his music, and coming in and singing on something he haven't heard before, it was something he wasn't used to do. He was trying to get that into his body so he could feel that music, but it wasn't that easy because it was someone else's lyrics. There was also the fact that they sing much faster where as King likes to sing the words longer, holding them, so he had to go in and change some of the words, taking some out but without changing the whole meaning. It was a big challenge for him, but it was also an experience he did really appreciated. He also really enjoyed the guys of this band.

The new King Diamond album, "House Of God", came out on June 20th 2000, and the American tour began on the next July 20th. The basic storyline was set in a real church called "Rennes-le-Château" in southern France that has an inscription across the door saying "Terribilis est locus iste" ("This place is terrible"), and when you walk inside, there's a figure of a devil greeting you. Actually this place has up to 120,000 visitors or tourists that come in there every year because there's a lot of mystery that surrounds this place; it's not common to have the devil greet you at a church, so a lot of people don't want to go in there because they believe that Satan is there. A lot of secret coded messages are inscribed on the walls. These talks about secret graves and people still have not found all of them. According to the history of the church, Jesus would have been there, living there, after he supposedly was crucified. Mary Magdalene, after Jesus died, would have been there too, having becoming his wife since. It was said that Jesus wouldn't have died on the cross but was saved and smuggled across the Mediterranean to this place, staying there until his death, many years later when he was very old. Francois-Bérenger Saunière, priest of that church from 1885 to 1909, would have discovered something which would have been, supposedly, four scrolls that indicated that Jesus would have been there after he would have been supposedly crucified. According to theories, the priest would have been paid vast sums of money by the Catholic Church to buy his silence on this secret, that would have seriously undermined the church's power if it would have been known by the believers. We can understand that if they found the proof that Jesus would not die on the cross, it would completely turn over the rules of faith because suddenly, the one who supposedly have died for our sins, wouldn't have died like the way the religion claims it. Then they would be in deep trouble, as all the faithful believers would realize something may have been wrong with what they have believed for so long. So the beginning of the album starts with that, and then the King Diamond story begins. So just like "The Eye", this album contains some elements of history, or at least, a legend that really lives on. The wolf and the main character were the only things completely made up for the album, but the surroundings and all the rest supposedly are there, according to the theories. King never went there personnally and hadn’t seen the landscape, and what was written in the album fit in extremely well, and after King saw some pictures from the place, he realized it's pretty much as what he thought it was, giving him the feeling that it was his own story, his own characters and experiences woven into that old legend there.

Originally, there was supposed to be another front cover: a black book on a crucifix, slanted, lying on purple cloth; the band has pictures of it. The black book, as people would probably have thought as the bible, would actually have been the "Necronomicon" instead, which is also the book from which were written two Mercyful Fate songs: "The Mad Arab" and "Kutulu (The Mad Arab Part Two)". King actually owns a hardcover version of the book that was given to him by the German ambassador's son of England as his son was out on tour with them and gave it to King. It was a limited edition of 666 copies and King has the number 666. Then, in the meantime, Hank sent to King with a cover he found which was drawn by Thomas Holm, who actually painted many other King Diamond and Mercyful Fate album covers prior to that. Originally, Hank wanted to use it for an upcoming Mercyful Fate album, but when King saw it, he really wanted it to become the cover of "House Of God". At this time, he was making the album, and it amazed him how he felt it represented the story. However, King kept the crucifix on the back of the CD. To offend no one, King decided not to put the cross upside down, but just the titles, so if you want to read them, so you have to flip the album upside down, thereby inverting the cross. The make-up King created for the album went in the same way, as he painted crosses in his face going both ways, showing the confusion of the mind, not knowing what is right and what is wrong religiously.

For the upcoming tour, they started a new coffin, just like the trick previously used on the "Conspiracy" tour. Since a while, King removed that trick because he almost died making it during a show, but now he wanted to bring it back. One time in Germany, the guy that was in charge of putting all the liquids to burn the coffin had to leave. However, his substitute was so nervous that he did put the liquid 45 minutes before the trick, instead of 5 minutes, as he was supposed to. So when King was slid into that coffin and they tried to close the end of it, those fumes were so heavy in there that King could barely breathe. Even if they had taken off the lid, and struck the torch, it would have exploded for sure. So King was kicking on the door, the little thing at the end of the coffin, that they were trying to close, to try and make them not able to close it, because then it would go wrong. King was kicking for his life, and they realized something was wrong as they couldn't close it; the more they were pressing, the more King was kicking. They finally took the coffin out without doing the trick. As they were working on that trick again, it almost went wrong again, so King then decided that it was enough. He didn't wanted to play with his life to do this thing; the coffin was old and so banged up, it didn't work the way it should, it became dangerous. Anyway, when it comes to pyrotechnics or anything to do with fire, it's always harder to get to perform as many are affraid of lawsuits if something goes wrong. King used to have lots of pyro in the earlier days, he always tried to go about everything the legal way. If he hadn't done it like that, there were many times he could have gotten away with it, but when you go the legal way, well he got stopped nearly half the time, where the fire marshall would say he couldn't allow that. Then King would hold a hundred dollar bill in his hand but they still never let him do things, so he had to build a stage show around not having those things, and just using them in the very few places he could. Some venues also gave him hard time for blowing fire from the goat's horns during Mercyful Fate's shows. Some flash paper was on the horns, and it got so warm that King have burned facial hair sometimes.

Then came out the new Usurper album, "Necronemesis", on September 12th. Note: Usurper also covered the song "Charon" on the "King Diamond Tribute" that have been released that same year.

A couple of weeks after that, David have been kicked out of the band about 7 months after his arrival. Even though he played good, it didn't worked out well personnally with the other guys in the band. There were also rumours saying that he had a very arrogant attitude on stage towards fans, even to challenge some of them to fight with him. The other members of the band couldn't stand such a bad attitude from a band mate so they fired him. The guy who came in to replace him was someone who previously was in the band a decade earlier: Hal Patino. Prior his return, Hal came down to Sweden, where the band rehearsed for a rock festival, just to say "Hi! Nice to see you back guys" and so on, as both King Diamond and Mercyful Fate always rehearses for one week before entering in the studio or starting a new tour. Hal also told the band that if they ever need a bass player some time in the future, that he would be interested to play again with them. So after the American tour, they called him, and everything turned out right with him. Ten years before, he had some problems that made the rest of the band not able to trust him anymore, but then he was no longer involved with any of the things he was involved with at that time. Shortly after that, right before Christmas, John Luke Hébert had a baby and left the band to concentrate on his family. Right after John's departure, as if it wasn't already enough, Glen announced that he would leave the band too. He just didn't have enough time for his personal life, his work, his other band, Eidolon, which he shared with his brother Shawn, in addition of playing with King Diamond. He also got married to a wife who brought a 10 year-old kid in the marriage. So during the Christmas vacations that followed, King and Mercyful Fate's guitarist Mike Wead talked about the problems with finding a replacement guitar player in King Diamond, so Mike told King that he could do the tour if King found no one else to fill the spot. King seemed very interested, but he told Mike he wanted him to be a permanent member of the band. Mike didn't know what to do since he wasn't interested in leaving Mercyful Fate, but King told him that he could stay in both bands just like him, so Mike finally came back officially in the King Diamond band. In the meantime, King had some discussions with former drummer Mikkey Dee to know if he would be interested in coming back in the band. Mikkey was interested in playing on the upcoming album, but not to stay in the band as a permanent member as he still was with Motörhead. On his side, King really wanted a full-time member, so he had to look for someone else. Finally, in January 2001, 30 year-old drummer Matt Thompson entered the band. Matt, who played drums since the early age of 9, previously was in the Michael Harris band, which also featured former King Diamond bassist David Harbour in 1996. Then King got his hands on a Michael Harris album on which Matt was performing. King liked a lot the drums on it and then contacted Matt for an audition, which was something that really made a dream come true for Matt who was a longtime fan of Mercyful Fate and King Diamond.

Then on February 19th 2001, King released an album which was actually recorded on September 30th 1980 during a rehearsal of his former band, Black Rose. It was recorded in a storage room under a bar in the outskirts of Copenhagen, which at that time served as the band practice facility. The band was practicing there 4 times a week, where it was loaded with many cases of beer; the band could drink as many as they wanted as long as they paid the owner at the end of each month, which they did. The actual recording quality is quite amazing in consideration that it was done live onto a 2-track reel to reel take recorder, using 8 microphones, which went through the band's 8-channel mixer and then straight to tape. This recording has been left untouched as we can hear people talking in between the songs and beers getting opened. This album was called "King Diamond & Black Rose: 20 Years Ago A Night Of Rehearsal". It contained 12 songs: 11 original Black Rose songs plus a cover of the Golden Earring's classic "Radar Love". They recorded their own songs on purpose and not all the covers that they normally did, so they would be able to go home and listen to it, maybe even improve on it. So, it was quite an interesting evening, they probably already warmed up by playing several Deep Purple covers before actually turning on the tape recorder. Of course, at the time, it was never meant to be released, even that King have often been tempted to steal a couple of riffs from it afterward. He first had the idea to release this rehearsal on CD in 2000 when a police officer in San Antonio, which is actually a good friend of King, was visiting him, and he brought up some of his friends who were King Diamond fans. They were sitting there, listening to music, when King remembered an old tape he had in his car, which actually was the contents of the Black Rose CD, and he made them listening to it. They all freaked out and wanted a copy, but King didn't want to. They told King that he should release it as it is part of his career, and it was specifically those people's idea that made him think about releasing it. He then told Brian Slagel, from Metal Blade Records, who was strongly interested to release it too. However, it had to be mastered but they couldn't re-mix it. For the release of this album, King got in touch with the other guys of Black Rose to let them know about the release; they were all really enjoyed about it. Also, they haven't seen themselves since many years. As of 2001, Kurt worked for a newspaper, Jesper worked at an office, Ib was a salesman and John worked at a library.