Baahubali is an epic story in which, a baby boy is miraculously found alive in the middle of a river by a few villagers. They raise him as their own. Named Shiva (Prabhas), the boy grows up to be an adventurous commoner until his past comes back to haunt him.
After a blockbuster movie Chatrapathi, director SS Rajamouli is once again working with Prabhas. In the ancient Kingdom of Mahishmati in India, a woman (Ramya Krishnan), decked in gold jewelry and highly injured, emerges from a cave adjoining a big waterfall, carrying a baby. She kills the soldiers pursuing her and sacrifices herself to save the baby, declaring that "Mahendra Baahubali must live!". Local villagers spot the queen carrying the baby while almost drowning in the river and rescue the infant. The queen's corpse is carried away by the current after pointing towards the mountain above the waterfall. Sanga (Rohini) and her husband name the infant Shiva and raise him as their own son. They seal the cave fearing that someone may come to take away the child.
Shiva (Prabhas) grows up to be a strong and adventurous young man aspiring to climb the mountain and makes many unsuccessful attempts at it. After successfully carrying a stone Shivalinga to the waterfalls, he then finds a mask which falls from the waterfall. Driven to find the owner of the mask, he attempts to climb the mountain again and succeeds this time.
On top of the waterfall, Shiva discovers that the mask belongs to Avanthika (Tamannaah), a rebellious warrior whose group has indulged in guerrilla warfare against king Bhallala Deva/Pallvalathevan (Rana Daggubati) of Mahishmati. The group led by Devasena's brother (Pruthviraj Balireddy), intends to rescue their former queen Devasena (Anushka Shetty ) who has been chained in the kingdom for the past 25 years. Avanthika is given the opportunity to rescue the queen.
Avanthika falls in love with Shiva after she finds out that he has climbed the waterfall for her. Shiva pledges to help her in her mission and sneaks into Mahishmati to rescue Devasena. Shiva rescues her and flees along with her but is chased down by the king's royal slave Kattappa (Sathyaraj), known for his great warrior abilities. After Shiva beheads Bhadra (Adivi Sesh), Bhalla Deva's son, Kattappa drops his weapon, realizing that Shiva is Mahendra Baahubali, the son of late king Amarendra Baahubali.
Kattapa begins to narrate the story of Amarendra Bahubali's past. Amarendra's mother died while giving birth to him, while his father had died long before that. Amarendra's uncle Bijjaladeva is deemed unfit to rule due to his crooked mentality, however he believes he is denied the throne as he is handicapped. Bijjaladeva's wife Queen mother Sivagami, takes charge of running the kingdom with Kattapa's assistance until a new king is elected. Amarendra Bahubali and Bhallala Deva are brought up together, trained in all areas including arts, science, disguise, politics, and warfare, but both of them have different approaches towards kingship. Amarendra Baahubali is gracious to everyone but Bhallala Deva is violent and achieves his goals by any means possible.
It is revealed that Mahismathi is about to be attacked by a army of savages, called Kalakeyas. Queen Sivagami sees this as an opportunity to find out who among her two sons should be future king of Mahismati. She declared that whoever kills the Kalakeya leader will be the future king and orders that Mahismatis war resources be distributted fairly among her two sons. The kalakeyas are given an opportunity to change their minds and walk away with their lives. The Kalakeya king rejects their offer and insults Queen Sivagami. An enraged Sivagami says she wants the Kalakeya king brought to her alive, so that she can feed him to the vultures.
Bijjaladeva (Nassar), Bhalladeva's father, uses his guile to make sure Bhalladeva gets the maximum war resources. When it seems that Mahishmati would end up being defeated, Amarendra inspires his soldiers to fight back and they end up crushing the enemy. While Amarendra defeated the king of Kalakeya and was about to obey the words of Sivagami by chopping his limbs, Bhalladeva swings his weapon from a distance and kills the Kalakeya king. Despite Bhalladeva being the one to kill the Kalakeya king, Sivagami announces Amarendra Baahubali as the new emperor because of his courage and leadership exhibited in the war and also because of the fact that he shielded and protected his own countrymen throughout the war.
After the flashback, when asked about Amarendra's current whereabouts, a tearful Katappa reveals that Amarendra is dead, and that he is one who killed Amarendra.