সাহাদেবের বিজয়যাত্রার কাহিনী শুরু হয় দন্তবাক্রকে পরাজিত করার মধ্য দিয়ে। দন্তবাক্র ছিলেন রাজাদের মধ্যে প্রধান, অসীম শক্তির অধিকারী। সাহাদেব তাঁকে পরাজিত করে কর গ্রহণ করেন এবং তাঁর রাজ্যেই তাঁকে পুনঃস্থাপন করেন। এরপর তিনি নিজের অধীনে আনেন সুকুমার এবং মানবদের মধ্যে শ্রেষ্ঠ, সুমিত্রকে। একইভাবে তিনি অন্যান্য মাছ্য, পাতচ্চরাদেরও দমন করেন। সাহাদেব দ্রুত নিশাদের দেশ জয় করেন, গোশৃঙ্গ পর্বতও তাঁর দখলে আসে। তিনি জ্ঞানী রাজা শ্রেণিমন্তকে পরাজিত করেন। মানবদের দেশ জয় করে তিনি কুন্তিভোজের কাছে যান এবং স্নেহভরে তাঁর আদেশ গ্রহণ করেন। তারপর তিনি চরমন্বতী নদীর তীরে যান, সেখানে তিনি জাম্ভকপুত্র রাজাকে দেখেন, যিনি পূর্বে তাঁর শত্রু বাসুদেবের দ্বারা পরাজিত হয়েছিলেন। সাহাদেব তাঁর সঙ্গে যুদ্ধ করেন এবং বিজয়ী হয়ে দক্ষিণ দিকে অগ্রসর হন। তিনি সেকন, অপরসেকন এবং আরও অনেক রত্ন সংগ্রহ করেন; তাঁদের সঙ্গে নিয়ে তিনি নর্মদা নদীর দিকে এগিয়ে যান। সেখানে তিনি শুনলেন, শক্তিশালী ক্ষত্রিয় ভগদত্ত, নারকপুত্র, ইতিমধ্যে অর্জুনকে কর দিয়েছেন। তাই সাহাদেব সেখান থেকে ফিরে আসেন। অশ্বিনীর পুত্র সাহাদেব, অসীম শক্তির অধিকারী, অবন্তির দুই বীর রাজা—বিন্দ ও অনুবিন্দকে, তাদের বিশাল সেনাবাহিনীর সঙ্গে যুদ্ধ করে পরাজিত করেন। রত্ন নিয়ে তিনি ভোজকাট নগরে যান; সেখানে দুই দিন ধরে যুদ্ধ চলে। তিনি ভীষ্মক, কোশলের রাজা, ভেনতাটার শাসককে পরাজিত করেন। কান্তারক, প্রাকোটক, নাটকেয়, হেরম্বক—এই সব রাজাদেরও তিনি যুদ্ধে দমন করেন। সাহাদেব মারুধাকে পরাজিত করেন এবং রম্যগ্রামকে জোরপূর্বক দখল করেন। তিনি নাচিন, আর্ভুক এবং আরও অনেক শক্তিশালী রাজাকে পরাজিত করেন। বনবাসী রাজাদেরও তিনি জয় করেন এবং নাটার অধিপতিকে নিজের অধীনে আনেন। পুলিন্দাদের পরাজিত করে তিনি দক্ষিণ দিকে যান। তখন তিনি পাণ্ড্য রাজার সঙ্গে একদিন যুদ্ধ করেন। সাহাদেব তাঁকে পরাজিত করে দক্ষিণ পথে অগ্রসর হন এবং কিষ্কিন্ধার বিখ্যাত গুহায় পৌঁছান। এই স্থান এক সময় বানররাজ বলির দ্বারা রক্ষিত ছিল, পরে কোশলের রাজা রামের অনুসারী সুগ্রীবের দ্বারা রক্ষিত হয়। সাহাদেব সেখানে প্রবেশ করেন এবং তাঁদের চ্যালেঞ্জ করেন। তিনি সাত দিন ধরে মৈন্দ ও দ্বিবিদ নামে দুই বানররাজের সঙ্গে যুদ্ধ করেন, কিন্তু কেউই পরাজিত হননি। তখন সেই দুই মহান আত্মা বানররাজ আনন্দিত হয়ে সাহাদেবকে বলেন, "হে পাণ্ডবদের মধ্যে শ্রেষ্ঠ, তুমি সব রত্ন নিয়ে যাও। বুদ্ধিমান রাজা যুধিষ্ঠিরের উদ্দেশ্যে তোমার কাজ যেন নির্বিঘ্নে সম্পন্ন হয়।" সাহাদেব রত্ন নিয়ে মহিষ্মতী নগরে যান। সেখানে তিনি রাজা নীলের সঙ্গে যুদ্ধ করেন। সাহাদেব, শত্রুদের বিনাশকারী, রাজা নীলের সঙ্গে ভয়াবহ যুদ্ধ করেন। তখন দেবতা অগ্নি তাঁকে সহায়তা করেন; অগ্নি সাহাদেবের সেনাবাহিনীতে আগুন লাগিয়ে মানুষের প্রাণের বিপদ ঘটান। তখন সাহাদেবের সেনাবাহিনীর রথ, ঘোড়া, হাতি, মানুষ এবং তাদের বর্ম অগ্নিতে দগ্ধ হতে দেখা যায়। এতে জনমেজয়ের মন চঞ্চল হয়, তিনি কোনো উত্তর দিতে পারেন না। ব্রাহ্মণ, কেন অগ্নি এইভাবে যুদ্ধে বিরোধিতা করলেন, যখন সাহাদেব যজ্ঞের জন্য চেষ্টা করছিলেন? মহিষ্মতী নগরে দেবতা অগ্নিকে একবার প্রেমিকের রূপে বন্দী করা হয়েছিল। রাজা নীলের কন্যা অত্যন্ত সুন্দরী ছিলেন; তিনি সবসময় অগ্নিহোত্র করতেন তাঁর পিতার জাগরণের জন্য। তাঁকে পাখা দিয়ে বাতাস করা হলেও, আগুন তখনও জ্বলত না, যতক্ষণ না তাঁর সুন্দর ঠোঁটের বাতাসে অগ্নি জ্বলে উঠত। তখন দেবতা অগ্নি সেই সুন্দরী কন্যাকে কামনা করেন, এবং রাজা নীল তাঁকে সকলের কাছে নিয়ে আসেন। পরে অগ্নি ব্রাহ্মণের রূপ নিয়ে সেই পদ্মনয়না, উচ্চনিতম্বা কন্যার সঙ্গে মিলিত হন; কিন্তু ধর্মপরায়ণ রাজা শাস্ত্রমতে তাঁকে নিষেধ করেন। এতে অগ্নি ক্রুদ্ধ হয়ে জ্বলে ওঠেন; রাজা বিস্ময়ে মাথা নত করেন। কিছুদিন পরে রাজা নীল মাথা নত করে আগের মতোই সেই কন্যাকে ব্রাহ্মণের রূপে অগ্নিকে দেন। সুন্দর ভ্রু বিশিষ্ট সেই কন্যা পেয়ে অগ্নি সন্তুষ্ট হন। অগ্নি, শ্রেষ্ঠ অন্নগ্রাহী, রাজাকে ইচ্ছামত বর দেন; রাজা তাঁর সেনাবাহিনীর নিরাপত্তা লাভ করেন। তখন থেকে, কোনো রাজা যদি অজ্ঞতাবশত মহিষ্মতী নগরী জয় করতে আসতেন, অগ্নি তাঁদের দগ্ধ করতেন। মহিষ্মতী নগরে কোনো নারীকে জোরপূর্বক গ্রহণ করা যেত না, শুধু তাঁদের সম্মতিতেই সম্ভব ছিল। অগ্নি এমন বর দেন, যাতে নারীরা সেখানে নিজের ইচ্ছার বিরুদ্ধে কখনও অপহৃত না হন, আর নগরীর রাজারা সেই ঋণ থেকে মুক্ত হন। তখন থেকে, রাজারা অগ্নির ভয়ে মহিষ্মতী নগরী শাসন করতেন। কিন্তু সাহাদেব, ধর্মপরায়ণ, তাঁর সেনাবাহিনীকে আগুনে ঘেরা ও ভীত দেখে, দ্বিধাগ্রস্ত হননি; তিনি জল স্পর্শ করে শুদ্ধ হয়ে অগ্নির উদ্দেশ্যে কথা বলেন।