On July 18th 1983, Mercyful Fate started recording at Easy Sounds Studios in Copenhagen for the 13 next days with producer Henrik Lund, which was the co-owner of the studio along with his brother. The band asked Henrik to produce the album, he was paid 1000$ by the record company. Even though the band had more time than when they did the first EP, time was precious and by chance, the band knew the songs very well before entering the studio and made it very quickly. They had to plan and calculate right as they had less than two weeks to record and mix the whole thing, so they really had not much time fooling around. It was an interesting challenge to prove themselves they could do it. While Henrik was mixing the album, the band were not allowed in the room; they had to wait outside the door, leaving him alone. He then had to come out, telling the band to come in listening to the mix he just have done. Then, when the band had comments, like putting less guitar or whatever, they had to leave again, waiting outside the door once more, waiting for him to do another mix, then come in again with more comments; the band found it very irritating. On the other hand, as Hank now recalls, it was wise on his part because with experience, you realize that too many people in the mixing room is not a good idea because everybody wants their own instrument louder or whatever, and that's probably why Henrik wanted to be left alone doing the mixing. When came the time to do the lead vocals, Henrik found it pretty different from what he used to know, as King brought a little altar in the studio, and some red lights as there was a specific feeling he wanted to create. It was a little spooky, and at first, when Henrik heard the lyrics, he was quite perplexed about it. After talking with King, and seeing everything was so natural for King, it was fine. At that time, the label asked the band to do a cover song, so the band tried Led Zeppelin's "Immigrant Song". The band skipped it because they didn't felt it was working very well. According to Hank, King's vocals were very surprising; it came really close to Robert Plant, so much that you could trick a lot of people into thinking it was actually Led Zeppelin.

It's on the following November 26th that "Melissa", the first full-length album was released. It have been very well acclaimed by both fans and critics and quickly became a huge hit, and this was also the first Mercyful Fate effort to get an official release in the United States, as the self-titled EP was a highly sought after import, and the BBC sessions were only availlable on bootleg tapes.

"Melissa" was the name of a skull the band was using at the time in their shows, and that we can see on the cover of the album. Originally, someone gave this human skull to King. Something happened to this person as it had a heavy blow on the forehead, the top had been cut off but it was still there, attached with a little hook. In the inside of the skull, there had been a big piece that had gotten loose but had grown back onto it on the inside, and there was a tiny little hole that you could see through from the outside to the inside. So, that person should have been hit with an axe or something, right in the forehead, and didn’t die from it obviously. So King started wondering what should have happened to this person, what fate could this person have had. For some reason, King had to make up his own little story to put his own mind at peace and that’s where the song “Melissa” came from, it was inspired by that skull. King thinks this could’ve been a witch, just like it could’ve been anything in fact, but that was just something to put himself at ease.

At a certain point, it almost seemed like the title-song was like the Bermuda Triangle, as something weird happened to this song: it did not have vocals over a certain part of the song when the album was originally released. But when Roadrunner Records later re-released it, suddenly there were new vocals over that same segment. Also, the first version had a very thick reverb on the voice, whereas the second version had no such processing on the voice. There was also a backwards message where King is saying "What message is this?". King finds it very interesting as maybe there are even more powers to that song. He still says that there is no way that it could have happened, which is mind-blowing to him. King has absolutely no clue about what could have happened with that, as it's a physical impossibility since you just can't add to vocals. The band have the 24-track master, so Roadrunner could never have gotten a hold of that, first of all, as they only have a finished master. They would never get a 24-track tape as it remained in the studio. What they would get could be a 1/2" master, which means that everything is mixed down. It's what they master the album from, so the only thing they could have done there, if somebody thought it was funny or whatever, go in and add some extra reverb or something. But then it would be through the entire thing; it would be guitars, bass, drums, everything, because you can't divide up tracks on a 1/2". Someone must have been interpreting King's vision, but probably not humans because it's physically impossible.

Some of the material on the album had their roots in even earlier demo recordings done during the Brats days, such as "Curse Of The Pharaohs", which was originally titled "Night Riders" on some old Brats demo, but retitled after King changed the lyrics to it as the original lyrics were written by the Brats bassist. There was also "Love Criminals", which is actually the first song Mercyful Fate ever written, that have been finally availlable for the first time on this album, but under the title "Into The Coven", which was originally meant to be the title of the album too. Also on this album, there was a song called "Satan's Fall" which, as Michael recalls, took ages to learn and had this eerie feeling the few times he heard it. As usual, Hank did the music for this song, and most nights, he would go out of bed going into his living room, sit there with his Stratocaster and compose. The band kept rehearsing it each time he added something until finally the song stopped, but as it always opened new doors, it always still grew more and more. There's something like 16 different riffs, and not only this was the band's longest song with a running time over 11 minutes (at least until the band released "Dead Again", on which the title track is 13 minutes long), but this song was actually written upon a book that would have a major impact on King's spiritual thoughts and philosophy; "The Satanic Bible", written by Anton Szandor LaVey in 1969. Fascinated by some occult experiences that happened to him in the past, King decided to read books about the occult, and a lot of things followed that. But most of the books he did read had the same view of Satanism; slaughtering babies, drinking blood, etc. He thought it was sick, but when he came across LaVey's Satanic Bible, he had the openness to read it anyway and to see what the hell was really going on. That was exactly what inspired the song "Satan's Fall"; discovering LaVey's Satanic Bible. After that, he began to investigate more deeply into the mystical side of life. King always lived by the Satanic philosophy even before he knew it was called like that. Even at that period of time, King used to have a black altar in his home, with two black candles always burning. In the middle of it was a human skull, and a gold, inverted cross. Concerning religion, King doesn't believe in any God or religion, for the simple fact that no one has any proof that what they believe in is the only true thing. If anyone had that, of course everyone else would believe in that because it was proven, and that’s why there is all these different religious directions, just as well as no one can prove that they believe in the right God, no one can prove that there is a God or that there is no God. King always been very open-minded to what the others may believe in and respects that; as everybody is different, he considers that its normal that everybody have their own beliefs as we can't all believe in the same thing. It also goes concerning the universe, which King believes we can't be alone as there's so much more we don't know yet.

On stage, King always wore the same type of make-up because it represents Death and it actually made him feel rather maniacal. They also used a few props to get people into a certain mood at their gigs rather than just nodding their heads to the music. One of King's favourite tricks was a thing the band once did in Eindhoven. One of their roadies gave them a small volume of his own blood, which King have put into a glass vial. They had two crossed goose feathers on their altar that night, and they would perform a Satanic ritual whereby human blood would be sprinkled on the feathers to make them alive. When they did it, King smashed the vial onto the altar, and then smeared his face in the blood. The fans obviously thought it was theatrical blood, and reached out to touch his hands. It was only then that they realized this was real blood, and some of them turned visibly ill. Unfortunately, they had to drop this part of the act, because although it had a great effect on the kids in the first two rows, anyone further back in the hall wasn't aware of anything happening.

In December 1983, the "Black Funeral" single was released. It contained a B-Side called "Black Masses", which was recorded during the “Melissa” session, but has been deleted from the album. As the first song recorded for the “Melissa” session, the sound wasn't there so the track was reduced to a B-Side only. During the same month, Mercyful Fate was booked to support Ozzy Osbourne in Copenhagen, but due to an illness on Ozzy's part, the show was cancelled. Later that same month, the band performed a headline show in Copenhagen as preparation for their upcoming European tour. It was also in 1983 that Mercyful Fate first met the guys of Metallica, with whom they stayed very good friends since then. It all began when Metallica, while recording some of its albums in Copenhagen, asked Mercyful Fate amplifiers and other borrowed equipments from them.

The European tour started in Holland on January 19th 1984 at The Dynamo, in Eindhoven. The next day, they performed a set at The Countdown Cafe in Hilversum, which was broadcasted live on local radio. In January 21st, they performed in Amsterdam, at The Paradiso Theatre, where the skull of Melissa has been stolen from the altar on stage by a fan due to very incompetent local security. Then the band went touring Italy on February, where they performed 6 shows, and on the following March 3rd, they started their UK tour supporting Manowar. Originally, 11 shows were booked, but it turned out that Mercyful Fate would only play one. That first and only show was taking place at St. Albans City Hall in Hertfordshire. When Mercyful Fate's crew arrived at the venue with their equipment at 2:00pm as agreed, Manowar's tour manager told them to leave the gear in the street until Manowar were finished with their soundcheck. At 7:30pm, they were finally allowed to bring in their equipment, leaving them only 30 minutes to do so; the doors opened at 8:00pm. Then, when the show started, Mercyful Fate have been told that they could only perform for 25 minutes, as opposed to the 45 minutes that they were guaranteed. Upon entering the stage, the band realized that their sound-engineer was denied access to the soundboard, naturally resulting in a terrible sound. At a certain point in the set, Manowar's sound-engineer began playing around with Mercyful Fate's sound. Then, it's been enough; they had no option but to demand some drastic changes if the tour was to go on. Even though Mercyful Fate's demands were backed up by their common record company, Manowar refused to comply. This forced Mercyful Fate to leave the tour and at a great financial loss to themselves. Not to mention the great dispair of their British fans.

On April 5th, the band played a sold out headline show at Saltlageret, in Copenhagen. There, for the first time, they were able to present their new chapel; a fantastic stage set in which the band had invested a lot of their earnings in their never ending quest to deliver the ultimate show for the fans. Then on April 30th, they began to work on the next release for the next 19 days, once again at Easy Sounds Studios. On June 10th, the band performed at the prestigious Heavy Sounds Festival in Poperinge, Belgium. Beside Mercyful Fate, the bill also featured Motörhead, Twisted Sister, Metallica, Baron Rojo, Lita Ford, H-Bomb and Faithful Breath. It was actually the first time the band played outside during the daylight. Playing when the sun is shining doesn't really fit to the songs which are quiet dark, so it loses too much of its atmosphere, but its a necessary evil as the band had to do it anyway, even though they prefered playing in the dark.