Evil's Soft First Touches - Hearts of Stone
This quest begins by visiting the Seven Cats Inn Notice Board in Velen. Your quest will update here and send you to Garin Estate way up in northern Novigrad. Head inside of the estate to have a talk with a group of thugs, so long as you don't call them a group of idiots there will be no fight. Olgeird von Everec is found upstairs.
Go through all of the dialogue with him until you return to the main room for some drink. In here you'll finally be able to accept the contract and leave this house. Outside you'll be stopped by a young woman who will give you the Rose on a Red Field Quest.
Now you'll have to head on over to Novigrad where the quest marker will lead you right to the sewer's entrance (pictured below).
Inside the sewers you will find large (apparently male) foot prints as well as smaller female foot prints. After fighting the single Drowner inspect that room to find a Drowner corpse with blade wounds (optional). To proceed go through the gate (follow the white dots on your compass) and you'll get a scene involving a nearby guard's body and one of your old friends, Shani.
She'll lead you to a gate which has been smashed in - use Aard on the wall next to it to blow it down then enter the next room. Explore the room and when you find the bodies of Shani's old comrades there will be a scene; after which you'll be tasked with finding the Skeleton Key. Inside of the quest circle there will be a body that has the blue dots floating up from it (typically signaling an important item), this body holds the key you need.
With the key in hand follow the white dots to the new quest marker and head downstairs where you'll battle it out with a couple of Drowners. After defeating the Drowners there will be another scene with Geralt examining the body here. When this scene is over you'll want to examine the body again to acquire a unique scent to follow. Before following it though I would recommend you take your time and loot everything down here - there is a TON of goodies.
This quest is pretty linear, so just follow the white dots on your compass any time you get lost, you'll eventually go through some wooden doors and find your way into the monster's lair. There will be a scene during which Geralt makes bait for the monster and draws it out. You'll be thrown into a fight with it right after.
Important: Geralt meditates before the fight which will knock off any Decoctions you have on you. Be sure to use them again before the fight begins.
Depending on your difficulty this may or may not be an extremely tough fight. He has a stomp attack he likes to use whenever you stay close to him for too long and he'll also swipe with his tongue if you're in front of him. There's also an acid spit ranged attack that he'll shoot at you if you're too far away for too long. Much like all frogs do, he also will hop around the battlefield which allows him to quickly close the gap between you if you get too far away.
Last but not least he will also create poison clouds on the ground which you will have to do your best to avoid (they'll place a DoT on you that tics for about 1/3rd of your health). First and foremost make sure you put Oil on your weapon since ever hit counts for this fight. I'd recommend using a Northern Wind bomb on him too as that'll freeze him and allow you to get a lot of hits in.
Toad Prince Weaknesses: Northern Wind (Bomb), Golden Oriole (Potion), Cursed Oil, Yrden
After the fight you'll get a cutscene of Geralt slicing open the toads belly and it transforming into a human. Some Olfiri will arrive in the sewers and drag you and their prince away. You'll awaken on a boat and there will be some dialogue and some scenes until you end up in a fight on a beach (pictured below).
This will actually be a pretty tough fight so you should go into your inventory and re-equip your gear and prepare yourself with any Potions or other goodies you may need. If you find this group of enemies too tough for you, running is also an option. Either way, once the fight is over head on over to Yantra where you'll meet up with your savior.
You'll need to meditate under the willows here until midnight at which point you'll get a scene and some more dialogue. For the final leg of this quest you will need to return to Garin Estate where you'll have a scene with Olgierd and O'Dimm. You can choose to fight Olgierd here if you wish but it's impossible to defeat him.
After speaking with Olgierd you'll have a one to one conversation with O'Dimm where he will tell you the specifics of what you need to accomplish. Once this quest completes you'll automatically receive Dead Man's Party and Open Sesame!
It doesn't matter what order you complete these quests in, both of them are required to be completed to continue with the Hearts of Stone Story Line.