Six months since the PCs rescued the jarl's daughters from the witch Sibbe, a new threat emerged from unknown shores. A messenger came to Silvermeade Hall, speaking of a series of attacks. Each time, a mysterious "Winter King" came to the coasts of towns and villages, making unreasonable demands and slaughtering when the fighting broke out. A few times his iceberg retreated, only to leave an unnatural winter in its wake, bringing famine and subjecting survivors to a slow death. His next route is the domain of Halfstead. In discussion with the war council, the jarl and the PCs and his advisors figure out the iceberg's likely route (thanks to Armund) and seek to attack him first in the middle of the ocean before he gets too close. Several longships are outfitted for war, and the jarl and the PCs set out for battle. Syrasi, a Nuklander elf recently hired to be the jarl's magical expert, tagged along as did the troll-kin warrior Vigbjorn.
Eventually after several days of sailing they come to a thick mist and strong storm, with a massive iceberg 3 miles in diameter adrift at sea. Misfortune occurs as soon as the ships set shore, for the Winter King's fell magic sends out giant icicles as siege weapons, forcing the ships to pull back as the PCs and One-Eyed Sven's team leaps to dry land. Weathering storms, undead warriors, and ice mephits, the party later finds Sven unconscious, as well as a giant bridge leading to a mysterious palace. Deciding not to leave him to die, the party does their best to tend to Sven's wounds and keep him warm as they continued exploring.
The western gates were heavily guarded by some surprisingly tenacious skeleton warriors, forcing the party to get their bearings and rest for a few hours. Around that time the jarl's main force circled around to the north side of the iceberg, ascended the cliffs, and assaulted the north side of the palace. After resting up and looting a nearby accounting house, the PCs saw some vikings engaged in combat around the plaza. The PCs helped them out, and got an update of the jarl's progress. The northeast section of the palace is being cleared out, but the undead warriors were very tough and so not much progress was made. The PCs decided to clear out the rest of the south side, finding a treasury with a magical shrunken boat, a lot of loot, and an old shrine to Althunak, an obscure demon god of frost who absorbed the souls of vanquished foes via cannibalism.
The PCs ascended the eastern spire to get a better vantage point. From below, peering down into the courtyard, the jarl's forces were matched up against equally fearsome zombie soldiers. Spotting a giant block of ice hanging by fragile chains, Askeladden relayed a message spell to the jarl of their plan while Syrasi got ready to loose a crossbow bolt at the chains.
The plan worked, the undead forces were tricked under the block as the jarl's party gave a false retreat. The party's efforts did not go unnoticed, as a series of long, slow claps emanated from across the bridge to the north. An armored man astride a skeletal steed was there, and his voice carried over clearly as though he were right next to them. Unusually talkative, the Winter King introduced himself as Prince Uth'ilopiq, of a long-dead civilization, and how he went by many names for his terrible deeds in service to his abyssal lord. He challenged the party to battle, but not before the tower on the far end blocked off the stairwell entrances with giant icicles, preventing any reinforcements in helping the PCs.
A pitched battle was held on the bridge. Two of the vikings with the party went down, Syrasi's glitterdust blinded his steed, and the Winter King's summoned winds nearly knocked Vigbjorn and Askeladden off the bridge. Heavily exhausted and wounded, with allies and summoned monsters falling alike, it was unclear who the victor would be. The tower was about to launch another icicle, this time at the docked northern ships, but not before the rest of Sven's team disabled it by killing the mages and jumping to the bridge to join the battle below (albeit a bit late).
But Askeladden struck the killing blow, and the Winter King, laughing, pulled himself deeper onto the blade, speaking in a whisper of how they struck the killing blow, but not before he tore open a "wound that will never heal." The iceberg was tied to his essence, and mere seconds later cracks in the earth and tremors threatened to rend the castle apart. Chaos descended around the party as the Winter King laughed moments before he was beheaded.
The party rushed as fast as they could, using the magical shrunken boat when it seemed that all was lost. The palace and its unholy legacy sank beneath the waves, as the party rejoined the jarl's ship, the Long Serpent, and set off back to Silvermeade Hall.
It was a joyous yet somber occasion. As people were thankful that the Winter King's reign of terror was brought to an end, so too did they mourn the many warriors who died that day to spare them his wrath. Bodies which were recovered were placed in ships set out to sea, lit by burning arrows as is custom. And a long, dark winter set in.
DM's Notes
I will admit that I made some minor alterations to the adventure, although the crux of it is more or less the same. Originally the Winter King's iceberg was but an unknown factor, and the party got there by going a-viking in exploring unknown waters. I decided to make Prince Uth'ilopiq a more immediate threat and played up the angle of Jarl Henrikson leading a raiding party to make war. I felt that this gave more of a "push" for the characters, both to act first before the iceberg got to Halfstead. The icicle siege weapons were originally just strong winds which blown the ships back, but this more obvious threat would better connect things as an obstacle to disable to help the longships safely approach and dock.
The Winter King was also originally intended to be fought in his throne room, but since it seemed that the party was wandering elsewhere and happened to be exploring next to a grand bridge I had their fateful encounter there instead.