सहदेवाने आपल्या दिग्विजय यात्रेत दंतवक्र या बलाढ्य राजाला पराभूत केले. त्याला आपल्या सामर्थ्याची जाणीव करून दिली आणि त्याच्याकडून कर घेत त्याला पुन्हा त्याच्या राज्यावर स्थापन केले. पुढे त्याने सुकुमार आणि पुरुषांमध्ये श्रेष्ठ असलेल्या सुमित्र या राजांना आपल्याखाली आणले. त्याचप्रमाणे, इतर मत्स्य राजा आणि पटच्चरांचा पराभव केला. निषादांची भूमी, गोश्रृंग नावाचा श्रेष्ठ पर्वत आणि शहाण्या श्रेणिमंत राजाला देखील त्याने सहज जिंकले. अशा प्रकारे अनेक भूमी जिंकून तो कुंतिभोज राजाकडे गेला. कुंतिभोजाने प्रेमाने त्याचे स्वागत केले आणि त्याच्या आज्ञेचे पालन केले. कर्मण्वती नदीच्या काठावर त्याला जंभकाचा पुत्र राजा भेटला, जो पूर्वी वासुदेवाकडून पराभूत झाला होता. या राजाशी सहदेवाने युद्ध केले आणि विजय मिळवून तो दक्षिणेकडे मार्गस्थ झाला. त्याने सेकन, अपरसेकन, आणि इतर अनेक मौल्यवान रत्ने घेतली आणि त्या राजासोबत नर्मदा नदीकडे गेला. त्याला कळले की बलशाली भगदत्त, नरकाचा पुत्र, याने आधीच अर्जुनाला कर अर्पण केला आहे. त्यामुळे तो पुढे न जाता परतला. मग अश्विनीकुमारांचा पराक्रमी पुत्र सहदेवाने अवंतीचे दोन शूर राजा – विंद आणि अनुविंद – यांना त्यांच्या विशाल सैन्यासह युद्धात पराभूत केले. त्यानंतर रत्न घेऊन तो भोजकट नगरीत गेला. तेथे दोन दिवस भीषण युद्ध झाले. त्याने भीष्मक या भयानक राजाला, कोसलाधिपतीला आणि वेणतटच्या राजालाही जिंकले. कांतारक, प्रकोटक, नाटक, आणि हेरंबक या सर्व राजांना युद्धात हरवले. मरुध, रम्यग्राम, नचिन, अर्बुक आणि इतर अनेक बलाढ्य राजे त्याने जिंकले. वनात राहणाऱ्या सर्व राजांना सहदेवाने आपल्या अधीन केले आणि नटाधिपतीलाही वश केले. पुलिंदांचा पराभव करून तो दक्षिणेकडे गेला. नकुलाचा धाकटा भाऊ असलेल्या सहदेवाने पांड्यराजाशी एक दिवस घनघोर युद्ध केले. त्यालाही जिंकून तो दक्षिण दिशेने पुढे गेला आणि प्रसिद्ध किष्किंधा गुहेवर पोहोचला. ही किष्किंधा पूर्वी वानरराज वालीने राखली होती आणि नंतर रामाच्या अनुयायी सुग्रीवाने तिचे रक्षण केले. सहदेवाने त्या स्थळी प्रवेश केला आणि सुग्रीवासमोर आव्हान दिले. तेथे वानरराज मैंद आणि द्विविद यांच्याशी सात दिवस युद्ध झाले, परंतु कोणताही वानर किंवा सहदेव पराभूत झाला नाही. शेवटी ते दोन महान वानर प्रसन्न होऊन, सहदेवाला म्हणाले, “पांडुपुत्रांमध्ये वाघासारखा असलेल्या योद्ध्या, सर्व रत्ने घेऊन जा. तुझ्या युधिष्ठिरासाठीचे कार्य यशस्वी होवो.” त्यानंतर सहदेवाने रत्ने घेऊन महिष्मती नगरी गाठली. तेथे त्याने नील राजाशी घनघोर युद्ध केले. पांडवांमध्ये शत्रूंचा संहार करणारा सहदेव त्या भीषण युद्धात सामील झाला, ज्यामुळे भ्याडांचे मन दडपले. त्या युद्धात अग्निदेव, होमाचा वहन करणारा, सहदेवाच्या मदतीस आला आणि सैन्याचा विध्वंस केला, लोकांच्या जीवाला धोका निर्माण केला. त्या वेळी सहदेवाच्या सैन्यात रथ, घोडे, हत्ती, सैनिक आणि त्यांचे कवच जणू अग्नीने पेट घेतल्यासारखे दिसू लागले. त्यामुळे कुरुवंशज, जनमेजय याचे मन गोंधळले आणि त्याला उत्तर देता आले नाही. ब्राह्मणांनो, असे का घडले की अग्निदेव सहदेवाच्या यज्ञकार्याच्या प्रयत्नात शत्रुत्वाने प्रकट झाला? महिष्मती नगरीत, अग्निदेव पूर्वी प्रियकराच्या रूपाने पकडला गेला होता असे सांगतात. नील राजाची कन्या अतिशय सुंदर होती; ती नेहमी आपल्या वडिलांच्या कल्याणासाठी अग्निहोत्र करत असे. तिच्या सुंदर, कपाळाच्या ओठांनी वारा फुंकल्याशिवाय अग्नी प्रज्वलित होत नसे. त्या सुंदर कन्येला अग्निदेवाने इच्छिले आणि राजा नीलाने तिला सर्वांना जवळ आणले. नंतर अग्निदेव ब्राह्मणाचे रूप घेऊन त्या कमललोचना, सुंदर नितंब असलेल्या कन्येला मिळाला; परंतु धर्मशील राजाने शास्त्राप्रमाणे त्यास मनाई केली. त्यामुळे क्रोधाने अग्निदेव प्रज्वलित झाला; हे पाहून राजा नील आश्चर्यचकित होऊन खाली वाकला. काही काळाने, नम्रतेने राजा नीलाने पुन्हा त्या कन्येला अग्निदेवाला – ब्राह्मणाच्या रूपात – अर्पण केली. राजा नीलाची सुंदर कन्या मिळाल्यावर अग्निदेव प्रसन्न झाला. त्याने राजाला इच्छित वर दिला; राजाने आपल्या सैन्याच्या रक्षणाचा वर मागितला. त्या दिवसापासून, जो कोणी राजा अज्ञानाने महिष्मती जिंकण्याचा प्रयत्न करतो, त्याचे सैन्य अग्नीने जाळले जाते. त्या नगरीत स्त्रियांना त्यांच्या इच्छेविरुद्ध घेता येत नसे; केवळ त्यांच्या संमतीनेच ते शक्य होते. अग्निदेवाने असा वर दिला की, त्या नगरीतील स्त्रिया त्यांच्या इच्छेविरुद्ध कधीच अपहृत होणार नाहीत, आणि त्या नगरीचे राजे त्यातून मुक्त झाले. त्या दिवसापासून, राजे अग्नीच्या भीतीने महिष्मतीचे राज्य करीत असत. पण सहदेव, धर्मनिष्ठ, आपल्या सैन्याला भीतीने वेढलेले आणि अग्नीने घेरलेले पाहूनही विचलित झाला नाही. त्याने पाण्याचा स्पर्श करून शुद्ध होऊन अग्निदेवाशी संवाद साधण्यास सुरुवात केली.