By sending the new demo tape plus some choice tracks off the Brats' rehearsal tapes to various labels and radio stations, one of these radio stations, the Holland-based Radio Hilversum, was the first to put some Mercyful Fate stuff on the airwaves and led to create a strong fan base for the band in Holland. In April 1981, King and Hank were being asked by Michael Denner to help him out recording a 5-track demo for his new band called Danger Zone. This demo, also recorded at The Rocktape Studios, contained songs such as "M.D.A." (which actually stands for Mission: Destroy Aliens), "Killed For Love" and "Not Amusing". There's some other songs which were recorded at that period which King finds very funny and guarantees no one will ever hear; songs like "Truck Driver", which talked about a guy driving a truck, were so far from the kind of thing King was doing; King didn't seemed to really enjoy Michael's songs. Rounding out the band was drummer 'Old' Nick Smith and bassist Timi Hansen, who is also known as Timi 'Grabber' Hansen. 'Grabber' was just a joke and put as a middle name some time later on tour when presenting him as a musician. The new demo turned out so well that it became obvious that the two bands should become one. The new lineup then featured King Diamond, Hank Shermann, Michael Denner, Timi Hansen, and 'Old' Nick Smith. However, the chemistry wasn't quite right and soon Ole Frausing replaced 'Old' Nick on drums. This new version of Mercyful Fate played their first live gig in the following summer in Taastrup, a small suburb of Copenhagen. Right from the start, the stage show included the classic visual effects of the exploding nun and the burning of a cross, all designed to give the crowd their money worth. During the next autumn, in Herlev, another suburb of Copenhagen, the band rehearsed and played one more gig. Once again, another lineup change took place. Michael had some problems finding the time to play with the band because he had a day job and a frustrated girlfriend so he left the band and was replaced by Benny Petersen, better known as 'Bennett'. Around the same time, Ole Frausing was asked to leave the band, and his replacement was Kim Ruzz, who have previously played with Benny. Kim Ruzz was flashy with a cool drumming style and hard-hitting playing, but was very different as a person compared to the rest of the other guys. He was younger and immature but was working very hard in the beginning, always six days a week.

In early 1982, Mercyful Fate had recorded two 4-track demos. The first one contained "Walking Back To Hell", "Running Free", "Black Masses" and "Hard Rocker", as the second one contained "Curse Of The Pharaohs", "Return Of The Vampire", "A Corpse Without Soul" and "Burning The Cross". Then co-manager John Kibble had been knocking on all the major label doors, but even though these demos received some attention from the underground tape-trading circuit, nobody was willing to take that big chance, although a lot of the A&R people liked what the band was doing. Prior to that, the band had already performed a few more headline shows and had also opened for a show of The Gillan Band in Copenhagen, on March 26th 1982.

Throughout his career, strange and occult things always happened to King, and one of those happened shortly after Mercyful Fate recorded these demos. That one happened in King's old apartment in Copenhagen, which some people already told him that it was haunted. There was King, his brother, as well another guy of the band (Timi or Kim); they were discussing whether they should listen to the demo right now or whether they should wait for the other guys to arrive before. They were sitting there, everybody opened their first beer; King's brother was sitting on the couch while King was sitting at the opposite to him on a chair. Suddenly, King's brother's glass rose something like 30 inches off the table out of thin air. It just came back down very slowly and landed on the table again without spilling a drop of his beer or anything. They just got all quiet. Nobody said a word, and they started looking at each other, as they quickly realized it wasn't their imagination; the three of them clearly saw the same thing! King usually feels very comfortable when things like that happen around him, because he sees the spirits as his protectors, almost as guardian angels, he feels very comfortable knowing that they're still around him. King later used that experience with the glass two years later in the song "Welcome Princes Of Hell" on the album "Don't Break The Oath", which was actually mispelled to "Welcome Princess Of Hell". The song "Ghost Of Change" on the "Into The Unknown" album is also related to that experiment in this song; this spirit or ghost came back to him and gives him another chance to change his path. King is actually being given the chance to relive his life, and as it all passes by, he's sure he doesn't need that ghost of change anymore.

In the following month of May, the band flew to Hull, England, to record a session for a newly established label Ebony Records, their A&R man, Daryl Johnston, liked a lot the material he heard from the band. He offered them the opportunity to do a session for 2 upcoming compilation albums on his label. The band then recorded "Black Funeral" and "Walking Back To Hell". "Black Funeral" was included on the "Metallic Storm" compilation album that came out during the following summer, which was the first album on which the band appeared. However, "Walking Back To Hell" have not been used at this time for a release. It was later renamed to "Death Kiss", and it is actually the song known as "A Dangerous Meeting". This version have later been released on the "Return Of The Vampire" compilation ten years later. A different version of this song have also been released: titled "Death Kiss" once again, a demo version have been added as a bonus track on the remastered version of "Don't Break The Oath" that Roadrunner Records later released in 1997. That version was actually the first known Mercyful Fate recording ever.

There, the band stayed in a private house, all of them in one room. The lady who owned this house provided them bed and breakfast, but she had only cold water to drink, which the band much or less enjoyed. On those two songs, Hank played both rhythm guitars because Benny, who got mad at his girlfriend, didn't show up in the studio the second day. While the band was staying there, they decided to go out to the cemetary opposite the house, just walking around getting some inspiration. Even though they were not doing anything criminal, they were not supposed to walk around there and when the police came around and saw them, five long-haired guys hanging around in the cemetary, they tried to catch them as the band ran away across the graves. They finally got back safely. During the summer that followed, Benny left because of his girlfriend, and Michael Denner went back in the band. From this point, this line-up had to remain the same until the demise of the band.

Then came the Dutch label Rave-On Records, offering the band their first record deal. Rave-On Records was based in the same city as Holland's leading heavy metal magazine Aardshock, which was a very supportive magazine of the band since hearing the demo recordings; that's what introduced the band to the label. So, in the following September, in Stone Sound Studios, Holland, the band recorded and mixed, in two or three days only, the 4 songs that had to become their classic eponymous EP, also known as "Nuns Have No Fun". While making that EP, the guys of the band all slept in one big room with a bunch of beds, a kind of dorm. During the recording, they really had a serious lack of time as some things have been made in such a rush that the EP didn't turned out as good as the band wanted. Some of the guitar solos on it were first takes, done under a lot of pressure. Producer Jac Hustinx, who was also the owner of the label, often allowed only one take for a lot of stuff Hank was doing, among others, such as the intro solo on "A Corpse Without Soul". No matter what they should have played, it would end on the record anyway because they just got no more time to do it. Even though the band was left dissatisfied with the quality of production, it was a major selling point to many fans who really liked its raw sound. This EP, which gave the band a lot of pressure, came out in the following month of November, but only in Holland. A song featured on this album, called "Devil Eyes", is actually the only Mercyful Fate song King doesn't like, because the beat reminds him of this kind of disco thing on the high hats; it just feels amateur to him and he always refused to play this song live. The cover art of the EP got some controversy, as at the time, the band got a flack because of their satanic stance. There was a priest in Denmark who really tried to finish Mercyful Fate's career, before the first EP came out, and they had the chance of appearing on national TV in Denmark. That was a big break, because back then, nobody knew them. This guy heard of them and wrote to all of the national papers trying to stop them. So King got really tired of listening to this guy, so the band did this EP with this nun being burnt by this coven on the cover, which was made purely to discredit that priest. King knew what he'd said when he saw it. He was all over the newspapers saying how dangerous Mercyful Fate were to the kids. Then King got his turn because they wanted to hear his side of it; King said to look at reality, as the cover was just a painting, while the Church burnt people for real. At this time, Mercyful Fate used a live 'nun' during their shows in Denmark: they were doing naughty things to her, as well as stripping her on stage. However, they didn't made a habit of the latter because there were not that many women prepared to go through such a ritual, as we can understand.

During the same month, the band had the opportunity to perform their first shows outside their native Denmark under the name Mercyful Fate. The first one took place at the famous Dynamo Club in Eindhoven, Holland, on September 23rd, as the club was packed with 300 people. That night, the crowd wanted to hear more and the band started to play their set again. The second show was at Ulicoten, still in Holland, two days later. The next day, the band returned to Copenhagen, where they were booked to support the English all-female band Girlschool. While Mercyful Fate was on stage, at one point, King said something like "We're gonna bring Satan into this house tonight". Then, when Mercyful Fate did ended its set, the guys went back into the dressing room. Some mimutes after that, King distinctly heard some strange noises coming from the PA; he still got a tape of it at his home, it was very strange. Then, one of the Mercyful Fate roadies came to tell them about the noises, and for some reason that King still doesn't understand, he turned to him and said "I know, and the band will have to stop playing in a few minutes and they won't play another note tonight!". Why that came out of his head, he can't explain. A few minutes later, while Girlschool was performing, their singer, Kim McAuliffe, who was using the same microphone as King used earlier that night, was electrified on stage and had to be taken to the hospital toward the middle of the set. What was even stranger was that the police called in some expert electricians to go over all the gear, and they could not find absolutely nothing wrong. The promoter of the gig went to the radio and said that he'd felt a very strange atmosphere surrounding the hall on that night, the like of which he'd never before come across. He told the DJ it was almost like something had to happen, it had been decreed by forces beyond human comprehension.

Then came an invitation from Tommy Vance, who asked them to record a live session for the Friday Rock Show on BBC Radio 1, in England. For the travel, the band bought an old blue Mercedes van, which they put their gear on the top of it. They could barely fit in these themselves with guitars on their laps and stuff like that; that's how they have been travelling back then. They arrived in London on March 18th, where they also performed their first show in England on that evening at The Moonlight Club in front of a small but very enthusiastic audience. This is on the next day that the band recorded the 3 songs for the BBC session: "Curse Of The Pharaohs", "Evil" and "Satan's Fall". These songs, recorded in only 8 hours in The Maida Vale Studios, were later mixed and produced by BBC engineer Tony Wilson. Just by the nature of live recording as opposed to a more involved studio production, these versions sounds a little more raw and in-your-face than the versions that would later have to appear on the album "Melissa". That same evening, they managed to perform at The Clarendon Ballroom, also located in the heart of London.

In early April, they returned in Holland to perform some shows that were set up by the people of Rave-On Records to coincide with the recording of their first full-length album. However, at that time, Mercyful Fate decided to leave Rave-On Records because they considered the label was too small, so they couldn't get the funds and the better terms for recording a full-lenght album, such as enough studio time to do full justice to the potential of the songs. Following that decision from the band, the label announced that the shows had to be cancelled because King had broken his leg, which of course, wasn't true. However, a good friend of the band, who worked for Aardshock magazine, had taken over the promotion of these gigs, and subsequently Mercyful Fate was able to perform as scheduled. Of course, that made Rave-On Records look rather ridiculous in the process.

Having returned to Denmark, the BBC broadcast of "The Friday Rock Show" was aired on April 22nd. After the broadcast, BBC had so many requests for a re-broadcast that they did it, and it really helped the band a lot. Among the listeners, there was also some people of Roadrunner Records of Amsterdam, Holland. They were then interested in signing the band for a long term contract and so, they contacted Mercyful Fate in May 1983. An agreement was reached and all the paperwork was left to the lawyers. On June 1st, the band then played a show in Copenhagen, and on June 25th, they were performing at the annually held Aardshock Festival in Holland. They played along headliners such as Accept, Raven, Vandenberg and Trance. In front of a crowd of over 6,000 crazed spectators, they really did a triumphant performance as they then signed a recording contract for 5 albums with Roadrunner Records. The next day they played in Bochum, in Germany, before returning home to start preparing the material for the upcoming recording sessions of their first full-leghth album.