ફિલ્મની સ્ટોરી કટપ્પા (સત્યરાજ) અને શિવુડુ ઉર્ફે મહેન્દ્ર બાહુબલી (પ્રભાસ) વચ્ચે સંવાદથી થાય છે. જે દરમિયાન સ્ટોરી ફ્લેશબેકમાં જાય છે. જ્યારે મહારાણી શિવગામી (રામ્યા કૃષ્ણન) બાહુબલી (પ્રભાસ)ના રાજ્યાભિષેકની જાહેરાત કરી હતી. પરંતુ તે પહેલા બાહુબલી અને કટપ્પા દેશ ફરવા માટે નીકળે છે. આ દરમિયાન બાહુબલીની મુલાકાત રાજકુમારી દેવસેના (અનુષ્કા શેટ્ટી)થી થાય છે અને પરિસ્થિતિ અનુસાર દેવસેના અને મહારાજ અમરેન્દ્ર બાહુબલી (પ્રભાસ) એક સાથે મહિષ્મતીમાં આવે છે. પરંતુ રાજ્યાભિષેક પહેલા સિંહાસન પર ભલ્લાલ દેવ (રાણા દગ્ગુબાતી)ની નજર હોય છે. આ માટે તે કટપ્પાની મદદથી એવું કરે છે જેથી અમરેન્દ્ર બાહુબલીનું અવસાન થઇ જાય છે અને રાજ્ય પર ભલ્લાલદેવનું સામ્રાજ્ય છવાઇ જાય છે અને તે દેવસેનાને બંદી બનાવી દે છે. હવે જ્યારે મહેન્દ્ર બાહુબલીને સમગ્ર બાબતની જાણ થાય છે તો તે ફરી એકવાર મહિષ્મતિ રાજ્યને ભલ્લાલથી આઝાદ કરાવવા માટે ભરચક પ્રયાસ કરે છે અને અંતે સત્યની જ જીત થાય છે.