सहदेव ने अपने विजय अभियान के दौरान सबसे पहले दंतवक्र जैसे महान और शक्तिशाली राजा को पराजित किया। दंतवक्र को अपने अधीन कर, उससे कर लिया और पुनः उसके राज्य में उसे प्रतिष्ठित किया। इसके बाद उन्होंने सुकुमार और पुरुषों के स्वामी सुमित्र को भी अपने वश में किया। इसी तरह, अन्य मत्स्य और पटच्चर राजाओं को भी उन्होंने परास्त किया। सहदेव ने शीघ्र ही निषादों की भूमि, गोश्रृंग पर्वत और बुद्धिमान श्रेणिमन्त राजा को भी जीत लिया। जब वे पुरुषों की भूमि को जीत चुके, तब वे कुन्तीभोज के पास पहुँचे, जिन्होंने स्नेहपूर्वक उनका स्वागत किया और उनकी आज्ञा को स्वीकार किया। फिर, सहदेव ने चर्मण्वती नदी के तट पर जंभक के पुत्र, एक राजा को देखा, जिसे पहले वासुदेव ने पराजित किया था। सहदेव ने उससे युद्ध किया और विजय प्राप्त कर दक्षिण की ओर बढ़ चले। उन्होंने शेकन, अपरशेकन और अनेक रत्न प्राप्त किए, और फिर उसके साथ नर्मदा नदी की ओर गए। जब सहदेव को ज्ञात हुआ कि बलशाली क्षत्रिय भगदत्त, जो नरक का पुत्र था, पहले ही अर्जुन को कर दे चुका है, तो वे वहाँ से लौट आए। फिर, अश्विनीकुमार के वीर पुत्र सहदेव ने अवन्ति के दो पराक्रमी राजाओं, विंद और अनुविंद, को उनकी विशाल सेना सहित युद्ध में पराजित किया। इसके पश्चात सहदेव रत्न लेकर भोजकट नगर पहुँचे, जहाँ दो दिनों तक भीषण युद्ध हुआ। वहाँ उन्होंने भयंकर भीष्मक, कोसल के स्वामी और वेनतट के शासक को भी परास्त किया। कंतरक, प्रकोटक, नाटक, और हेरंबक राजाओं को भी सहदेव ने युद्ध में हराया। उन्होंने मरुध और रम्यग्राम को बलपूर्वक जीता, साथ ही नचिन, अर्बुक और अन्य बलशाली राजाओं को भी पराजित किया। पाण्डु पुत्र सहदेव ने इन सभी वनवासियों को अपने अधीन किया और नाटा के स्वामी को भी वश में किया। पुलिंदों को युद्ध में हराकर वे दक्षिण की ओर बढ़े। वहाँ, नकुल के छोटे भाई सहदेव ने पाण्ड्य देश के राजा से एक दिन तक घमासान युद्ध किया और विजय प्राप्त की। इसके बाद वे दक्षिण के मार्ग से आगे बढ़े और प्रसिद्ध किष्किन्धा गुफा तक पहुँचे। यह वही स्थान था, जहाँ पहले वानरराज बालि का शासन था और बाद में राम के अनुयायी सुग्रीव ने वहाँ राज्य किया। सहदेव ने वहाँ प्रवेश कर उन्हें चुनौती दी। वहाँ सहदेव का सात दिनों तक वानरराज मैंद और द्विविद के साथ युद्ध हुआ, परंतु दोनों वानरराजों ने हार नहीं मानी। अंततः वे दोनों महाबली वानर प्रसन्न होकर सहदेव से बोले, "हे पाण्डवों में श्रेष्ठ! सभी रत्न लेकर जाओ, तुम्हारा कार्य युधिष्ठिर के लिए निर्विघ्न संपन्न हो।" इसके बाद सहदेव रत्न लेकर महिष्मती नगर पहुँचे, जहाँ उनका राजा नील से भयंकर युद्ध हुआ। पाण्डवों में शत्रु सेनाओं के संहारक सहदेव ने वहाँ ऐसा भीषण युद्ध किया कि डरपोक जन भयभीत हो उठे। उस समय अग्नि देव, जो देवताओं के लिए हवि ग्रहण करते हैं, सहदेव की सहायता के लिए प्रकट हुए। अग्नि ने शत्रु सेना का संहार किया और पुरुषों के प्राण संकट में डाल दिए। सहदेव की सेना में रथ, घोड़े, हाथी, सैनिक और उनके कवच अग्नि में जलते दिखाई दिए। यह देखकर कुरुवंशजों का मन अत्यंत व्याकुल हो गया, और जनमेजय उत्तर देने में असमर्थ रहे। तब ब्राह्मणों ने पूछा, "यह अग्नि देव सहदेव के यज्ञ कार्य के लिए प्रयासरत रहते हुए युद्ध में शत्रु क्यों हुए?" दरअसल, महिष्मती नगरी में अग्नि देव को पहले एक प्रेमी के रूप में पकड़ा गया था। राजा नील की कन्या अत्यंत सुंदर थी और वह सदा अपने पिता के लिए अग्निहोत्र करती थी। जब भी उसे पंखे से हवा की जाती, अग्नि तब तक नहीं प्रज्वलित होती जब तक उसकी सुंदर कपोलों की वायु से अग्नि प्रज्वलित न हो। तब अग्नि देव ने उस सुंदर कन्या की अभिलाषा की और राजा नील ने उन्हें समीप ला दिया। फिर, अग्नि देव ब्राह्मण का रूप धारण कर, संयोगवश उस कमर सुंदरी, कमल-नेत्री युवती के साथ रमण करने लगे। परंतु धर्मनिष्ठ राजा ने शास्त्रों के अनुसार उन्हें रोका। इससे कुपित होकर अग्नि देव प्रज्वलित हो उठे। यह देखकर राजा नील चकित होकर सिर झुका कर भूमि पर प्रणाम करने लगे। कुछ समय पश्चात् राजा ने सिर झुकाकर उस कन्या को, पूर्ववत, ब्राह्मण रूपी अग्नि को समर्पित कर दिया। राजा नील की उस सुंदर भौंहों वाली कन्या को पाकर अग्नि देव प्रसन्न हुए। अग्नि, जो हवि ग्रहण करने वाले श्रेष्ठ हैं, उन्होंने राजा को इच्छित वरदान दिया और राजा ने अपनी सेना की रक्षा का वर प्राप्त किया। तब से, जो भी राजा अज्ञानवश बलपूर्वक उस नगर को जीतना चाहता, वह अग्नि से भस्म हो जाता। महिष्मती में, हे कुरुवंशी, स्त्रियों को बलात् नहीं ले जाया जा सकता था; वे केवल अपनी इच्छा से ही दी जाती थीं। अग्नि ने यह वर दिया कि वहाँ की स्त्रियों को उनकी इच्छा के विरुद्ध नहीं छीना जा सकता, और नगर के राजा इस ऋण से मुक्त हो गए। तभी से, हे भरतश्रेष्ठ, अग्नि के भय से वहाँ के राजा सदैव विधिपूर्वक नगर का शासन करते रहे। परंतु धर्मात्मा सहदेव, जब अपनी सेना को अग्नि से घिरा और भयभीत देखा, तो विचलित नहीं हुए। उन्होंने जल स्पर्श कर अपनी शुद्धता प्राप्त की और फिर अग्नि से निवेदन किया।