A prophecy states that a female child with a special birthmark will herald the downfall of the evil sorceress Queen Bavmorda. Bavmorda imprisons all pregnant women in her realm to prevent fulfilment of the prophecy. When the prophesied child is born, the mother begs the midwife to take her to safety. The midwife reluctantly accepts and leaves Nockmaar castle unnoticed. The mother is executed and the midwife is eventually found. Knowing she cannot escape, she sets the baby on a makeshift raft of grass and sends her down the river hoping for fate to run its course. The midwife is then killed by Nockmaar hounds. Bavmorda sends her daughter Sorsha and General Kael to find the baby.
The baby drifts downriver to a Nelwyn village. She comes into the care of Willow Ufgood, a kind farmer and conjurer who hopes to become a sorcerer; his wife Kiaya and his children fall in love with the baby immediately, and Willow too soon grows to love her as one of his own. During a town festival the village is attacked by a Nockmaar hound which is quickly killed by the village warriors. The High Aldwin, the village sorcerer, learns about the baby and selects Willow, due to his devotion to the child, to accompany a party of volunteers returning the baby to the Daikini (human) people. At a crossroads, they find a human warrior named Madmartigan trapped in a crow's cage. The rest of the party want to give the baby to Madmartigan and go home immediately, but Willow and his friend Meegosh refuse, so the others leave. After spending the night at the crossroads, and meeting an army led by Airk Thaughbaer, an old friend of Madmartigan's, marching against Bavmorda, Willow reluctantly decides to free Madmartigan so that he can take care of the baby for them.
Later on, the baby is stolen by a group of brownies. While chasing them, Willow and Meegosh are trapped, but rescued by Cherlindrea, a Fairy Queen, who identifies the baby as Elora Danan, the future princess of Tir Asleen and Bavmorda's bane, and assigns Willow the task of helping the baby fulfil her destiny. Willow sends Meegosh home, and two of the brownies, Franjean and Rool, are instructed to guide Willow to the sorceress Fin Raziel. The three of them later encounter Madmartigan at a tavern, where he is disguised as a woman to hide from Lug, a cuckolded husband, who then flirts with the disguised Madmartigan. Sorsha arrives and reveals his identity, and in the ensuing brawl started by the furious Lug upon realisation that Madmartigan is not a woman, Willow, Madmartigan and the brownies escape. Madmartigan guides them to a lake where Raziel lives, but departs again as they cross it.
Raziel has been transformed into a possum by Bavmorda, and Willow and his party return with her to shore. They are captured by Sorsha, who already has Madmartigan in custody, and are taken to a snowbound mountain camp of the Nockmaar army. Willow tries to restore Raziel, but turns her into a rook instead. Madmartigan is dosed with love dust by the brownies and declares his undying love for Sorsha. The prisoners escape and reach a village at the foot of a mountain, where they again encounter Airk and the remains of his army, recently defeated by Bavmorda's forces. Madmartigan proclaims his loyalty to the Nelwyn and promises to protect Willow and Elora.
With Sorsha as their temporary hostage, they escape to the castle of Tir Asleen, but discover that its inhabitants have all been frozen by Bavmorda and the castle is overrun by trolls. The castle is surrounded by Kael's army. During Kael's assault on the castle, Sorsha realizes she also loves Madmartigan and decides to join him and Willow in opposing her mother's army. Willow accidentally turns a troll into a massive, fire-breathing, two-headed monster that turns the tide of the battle, and Airk arrives with his army to assist. However, Kael captures Elora and returns to Nockmaar, where he reports Sorsha's betrayal to Bavmorda.
Airk's army, Willow, and the others arrive at Nockmaar to lay siege, but Bavmorda turns the soldiers into pigs. Instructed by Raziel, Willow protects himself with a spell and avoids transformation. He succeeds in turning Raziel into a human again, and she restores the others to their original forms. Willow's group tricks their way into the castle and start a battle. Airk is killed by Kael, who is in turn slain by Madmartigan after a lengthy sword duel. Sorsha leads Willow and Raziel to the ritual chamber where they interrupt Elora's sacrifice. Bavmorda and Raziel have a magical duel, during the course of which Raziel is incapacitated. Willow uses a "disappearing pig trick" he had performed as a conjurer to fool Bavmorda into thinking that Elora was sent out of her reach. Lunging at Willow, Bavmorda accidentally triggers the ritual's final part to send Elora's soul to oblivion and banishes her own soul instead.
Willow is rewarded with a magic book to aid him in becoming a sorcerer, and Sorsha and Madmartigan remain in Tir Asleen to raise Elora together. Willow returns home to a hero's welcome and is happily reunited with his family.

Question: What do they discover upon arrival to Tir Asleen?
Answer: Everyone in Tir Asleen has been frozen by Bavmorda and there are trolls in the castle.