In Kievan Rus', at the time of Prince Vladimir the Great (Vanda in the English dub), the Asiatic barbarians known as the Tugars (and their leader, Tsar Kalin) are ravaging and pillaging the land. A group of pilgrims pleads with the giant knight Svyatogor (Invincor in the dub) to join in their fight, but he says he is too old and too heavy for the earth to support him, so he gives them his sword to pass on to a new bogatyr (roughly "knight errant") before he and his horse turn to stone.
In the farming village of Karacharovo, the powerfully built but paralyzed Ilya Muromets can only sit helpless at his window as a horde of Tugars, led by warrior Sartak, raid the village and kidnap his beloved, Vassilisa (Vilya in the dub). They subsequently attack the caravan of the wealthy boyar Mishatychka; as Vassilisa watches, he promises to serve the Tugars as a double agent if they spare him. Sartak makes him swear a blood oath that he will send word to them at the Kosozh Rapids by Peroun's Day that he has destroyed the bogatyrs of Prince Vladimir from the inside; if he fails, they will kill him.
Meanwhile, the pilgrims who received Svyatogor's sword arrive in Karacharovo, and are so impressed by Ilya's Patriotic Fervor that they decide he is worthy of the sword, and they give him a magic herb and accompanying song to cure his paralysis. Though his parents are delighted to see him walk at last, he insists that he must leave to join the fight against the Tugars, and neighbouring farmer Mikula Selyaninovich gives him a foal named Chestnut Gray, who grows into a massive steed after being bathed in the morning dew of the mountains for three days.
At a crossroads where he is told he will be killed if he goes straight ahead, married if he goes left, and rich if he goes right, Ilya decides to take his chances with the supposedly lethal dangers straight ahead, and he is soon face to face with the wind demon Nightingale the Robber, who blows wind so hard it parts the forest backward. Ilya defeats him by throwing a cudgel at him to knock him off his branch and takes him to Kiev to present to Prince Vladimir for judgement.
In Kiev, the carpenter Razumey has been arrested for stealing wood, but Prince Vladimir pardons him when he explains that he plans to use the wood to build ballistas to aid in Kiev's defence. The bogatyr Dobrynia Nikitich returns from a successful peace negotiation with a neighbouring kingdom, and a celebratory feast is called, other guests at which include Dobrynia's fellow bogatyr Alyosha Popovich. Ilya arrives during the feast and is able to contradict Mishatychka's claims that he has killed Nightingale by producing him alive. As the demon is taken away to his fate, Prince Vladimir gives Ilya a ring and makes him part of a trio with the duly impressed Dobrynia and Alyosha.
Tugar herald Idolishche Poganoye, a massive fat man on an impossibly larger moving platform, interrupts the celebrations and tells Prince Vladimir that he must pay twelve years' worth of tribute to Tsar Kalin or face his armies' wrath. In the ensuing argument between the envoy and the three bogatyrs, the former throws a sword at Ilya, who throws the sword back at Idolishche, killing him. Most of the other Tugars are routed by Ilya using the corpse as a club, while the rest run off. With Peroun's Day fast approaching, the worried Mishatychka decides getting rid of Ilya is now his top priority.
Ilya is still pining for Vassilisa, and asks Prince Vladimir and his wife, Princess Apraksia, for an assignment befitting a knight. He is sent to the border post of Starodubovets, and on the way there, he re-encounters the Tugars who kidnapped Vassilisa and is able to free her. They are soon married, and when duty calls him away again, Ilya gives the now pregnant Vassilisa the ring Prince Vladimir gave him and tells her to pass it on to their son, whom he asks her to name Little Falcon (in honour of the falcons who saw their love for each other in their home village), and whom he hopes will grow up to be a bogatyr like his father. She joins a caravan back to Karacharovo under the leadership of the boyar Matvei Sbrodovich, but the caravan is attacked by the Tugars, Matvei is wounded, and Vassilisa is re-captured.
Matvei survives for long enough to report back to Prince Vladimir, who wonders who Ilya was not there to defend the caravan, and Mishatychka uses the opportunity to tell lies about Ilya's aspirations to depose the prince and rule Kiev himself. The other boyars, who also see Ilya as an obstacle to their own ambitions, corroborate the lies, and Ilya is imprisoned in the castle dungeons, leading Dobrynia and Alyosha to quit the prince's service in protest.
Meanwhile, the captive Vassilisa has given birth to a son, Little Falcon, whom Kalin decides to raise as his own, and although he gets Mishatychka's Message in a Bottle at the Kosozh Rapids about the bogatyrs' downfall (well, a pair of his trousers that got caught in one of Razumey's hunting traps when the latter surprised him as he was throwing the original message into the River Dnieper), he decides to delay the invasion until Little Falcon grows up and can fight alongside them. In just ten years, he has the build and strength of a man twice his age, so Kalin leads the Tugars toward Kiev.
When Prince Vladimir receives their demand for seven hundred carts of gold in three days, he is powerless to resist, and decides he must free Ilya and make amends with him. Mishatychka claims Ilya must have starved to death long ago (he has been secretly throwing Ilya's food away rather than serving it to him, and now claims the prisoner was refusing to eat), only to discover that he has had an endless supply of food from a magic cloth Vassilisa wove for him when they were last together. Mishatychka is sent off to be boiled in pitch, while Ilya agrees to ride out against the Tugars out of love for his country, not for Prince Vladimir. The pilgrims who cured his paralysis relay word of his release to Dobrynia and Alyosha, who make their way back to Kiev.
Three days pass, and Ilya hatches a plan to buy more time by tricking Kalin with torn sacks and broken carts to create the impression that all of the gold being paid as tribute fell out during transport. The supposed search for the gold takes a day. Then, the Tugars are forced to give Kalin a mountain of the gold they, apparently, wanted to keep for themselves (much of which was actually already their own money). This takes about one day more. Then, Kalin demands Ilya Muromets, and the supposed search for him takes two more days. Ilya gets Kalin frustrated enough to claim that he'd cancel the invasion if the hero would stand before him; Ilya promptly reveals himself to Kalin — who feels insulted by this deception and decides to attack anyway. Ilya escapes, having bought enough time for Dobrynia and Alyosha to return, and the three bogatyrs rally the armies to defend Kiev.
Little Falcon is sent forth as the vanguard of the Tugar attack, and he issues a personal challenge to Ilya. While they duel, Ilya sees the ring he received from Prince Vladimir on Little Falcon's finger, and he reveals the boy's true heritage to him. Little Falcon switches sides and joins the Kievan armies, but Ilya gives him a more important mission: free his mother and the other prisoners from Tugar captivity. While mother and son are re-united, Ilya, Dobrynia, and Alyosha each lead an army against the Tugars, with Alyosha personally impaling Sartak, Vassilisa's original kidnapper from years earlier.
Kalin orders his men to form a human mound from which he can survey the battlefield, but when an arrow from one of Razumey's ballistas knocks him off his perch, he orders the three-headed dragon Zmey Gorynych (Zuma the Dragon in the dub script) to attack the Kievan armies. The ballistas soon bring the dragon out of the sky, and Ilya severs one of his heads, Alyosha severs a second, and Little Falcon and Ilya team up to sever the third. The Tugars are defeated, Kalin is taken prisoner, and Ilya and Vassilisa are re-united. Ilya declines Prince Vladimir's offer of elevation to the nobility and instead passes Svyatogor's sword on to Little Falcon, who follows in his father's footsteps as a bogatyr.
The film closes with a close-up of Ilya declaring "The Russian people have delivered Rus'!"
