The story of SuperTux focuses on Tux the penguin who has to save his beloved girlfriend Penny from the clutches of the evil Nolok.
(Plays at the start of the game - see also Milestone 1 version)
" Somewhere at the shores of Antarctica... "
Tux and Penny are shown having a picnic at the antarctic shore. In the background, there's an ice bush, which eventually starts shaking a bit, attracting the focus of the camera. Suddenly, Nolok jumps from behind the nearby ice bush and summons a bright flash with his mighty sceptre. The flash blinds Tux and Penny gets captured in the process. Nolok has only left a small note behind.
The note reads: “Tux, my arch enemy! I have kidnapped your beloved Penny and have taken her to my fortress. The path to my fortress is littered with my minions. Give up on the thought of trying to reclaim her, you don't have a chance of saving her! Signed, Nolok”
As Tux looks up he sees Nolok's castle appear foggily in the distance. Realizing the trouble Penny could be in, Tux becomes determined to save her, thus beginning his journey.
(Plays after finishing the level "The End of the Tunnel")
Tux walks out of the ice cave but stops as he hears a strange sound in the distance. A yeti appears to be watching him from higher up on a small incline. Before Tux can do anything, however, the yeti runs away. Tux is concerned by the yeti's sudden retreat but decides to continue his journey as he has spotted the castle, in the same direction the yeti went.
(Plays at the end of the level "Castle Of Nolok")
Tux reaches an empty throne room with nothing but a letter hanging on a pillar. A letter by Penny that mentions Nolok having tricked Tux and taking off with her to a far forest. Tux hears the yeti who runs towards a door nearby. He opens the door and finds himself on a balcony outside the castle walls and jumps. The yeti chases him down to a small ravine, leaving Tux no other choice than to fight the yeti.
(Plays after beating the Yeti)
The yeti is beaten. Rubbing his head and angrily grunting, the yeti communicates his disbelief. When asked by Tux if he knew where Nolok went and how he could get there the yeti just laughs at the him. While further tantalizing Tux about his cluelessness the yeti accidentally reveals the location of the forest and where to find a boat to travel with. Realizing this, the yeti leaves the scene before revealing even more infomation. Tux now knowd where he must go and sets off towards the glacier isle to find the crystal mine.
(Plays immediately after setting foot on world 2)
A long trip to the north with a boat and Tux finally manages to reach the southern lands of Rooted Forest. Upon setting shore, Tux hops out of his boat and takes his first steps in the grass. Tux has a small inner monolog while wandering around, looking where to go. He decides to find some place higher up to get a better view of the land, since he has no idea where Nolok could have stationed his forest castle.
(Plays right before the corrupted forest)
Astonished by the scale of the forest and the much warmer temperatures Tux continues his search for Nolok and Penny. After a long journey through the woods, rough weather and a dark underground tunnel, something very strange started happening. The trees and bushes, the entire forest terrin begins to slowly change. Plants rot away, turning bluish purple, covered in thick dark green vines. Dark purple roots break through the ground, the sky get dark and cloudy. Eerie wisps and living flames emerge. Nolok's minions Tux encountered before are affected too, looking much more menacing and eerie, but also... worried. Some are even covered in purple roots. Tux feels uneasy but pushes forward. He spots a tower in the distance and heads off towards it.
The scene then cuts to Nolok who says that Tux has done well to get so far through the forest, but will not get past the dangers in of the corrupted forest.
(Plays at the end of the tower level of Rooted Forest)
Tux reaches the top of the tower but still cannot find Penny or Nolok. The tower suddenly begins to crumble. Dark purple roots tear down the building and Tux flees. Close by the Ghost Tree awaits him. Tux takes a deep breath and prepares to battle.
(Played after beating the Ghost Tree)
Tux is shown combating the forest boss. The ghost tree withers away and the forest returns back to normal...
Once Tux reaches the end of Rooted Forest, Nolok starts to notice Tux's determination being impressed by his commitment and bravery to push through even leaving his homeland. After defeating Nolok and rescuing Penny, Nolok acknowledges Tux and Penny's bravery shown a more honorable side. He claims to not change his ways due to his nature as a predator, but that he respects the two as his equals.
(Note: Should Nolok ever capture her again or perhaps Tux, he would do it for the entertainment of them having to go through his challenges again.)