સહદેવે દંતવક્ર જેવો મહાબલી રાજાઓનો અધિપતિ હતો, તેને પણ પોતાના પરાક્રમથી પરાજય આપ્યો અને તેને શ્રેષ્ઠ રાજસિંહાસન પર બેસાડી, પોતાને કર અર્પણ કરાવ્યો. ત્યારબાદ તેણે સુકુમાર અને મનુષ્યોના સ્વામી સુમિત્રને પણ પોતાના વશમાં કર્યા. એ જ રીતે અન્ય મત્સ્ય અને પટચ્ચર રાજાઓને પણ સહદેવે જીત્યા. પછી તેણે ઝડપી રીતે નિષાદોની ભૂમિ, ગોશૃંગ નામના પ્રસિદ્ધ પર્વત અને વિદ્વાન શ્રેણિમંત રાજાને પણ વિજય કર્યો. મનુષ્યલોકને જીત્યા પછી, તે કુંતિભોજ પાસે પહોંચ્યો, અને પ્રેમપૂર્વક તેની આજ્ઞા સ્વીકારી. પછી, ચર્મણ્વતી નદીના કિનારે, તેણે જંભકપુત્ર રાજાને જોયો, જેને અગાઉ વસુદેવ દ્વારા હરાવવામાં આવ્યો હતો. સહદેવે તેની સાથે યુદ્ધ કર્યું અને તેને વિજય કરીને દક્ષિણ દિશામાં આગળ વધ્યો. તેણે શેકન, અપરશેકન અને અનેક અન્ય રત્નો મેળવ્યા અને ત્યારબાદ તે નર્મદા નદી તરફ ગયો. ત્યાં તેણે જાણ્યું કે ભગદત્ત, નરકપુત્ર અને મહાબલી ક્ષત્રિય, પહેલેથી જ અર્જુનને કર અર્પણ કરી ચૂક્યો છે; તેથી તે ત્યાંથી પાછો ફર્યો. પછી, અશ્વિનીપુત્ર સહદેવે અવંતિના વિંદ અને અનુવિંદ નામના બે પરાક્રમી રાજાઓને, તેમના વિશાળ સેના સાથે યુદ્ધમાં હરાવ્યા. પછી, રત્નો લઈને તે ભોજકટા શહેર પહોંચ્યો, જ્યાં બે દિવસ સુધી યુદ્ધ થયું. ત્યાં તેણે ભયંકર ભીષ્મક, કોશલના રાજા અને વેણટટાના શાસકને પણ જીત્યા. સહદેવે કંતરક, પ્રકોટક, નાટકેય અને હેરંબક રાજાઓને પણ યુદ્ધમાં હરાવ્યા. મારુધ અને રમ્યગ્રામને પણ જીત્યા, તેમજ નચિન, અર્બુક અને અન્ય મહાન રાજાઓને પણ પરાજય આપ્યો. પાંડુપુત્રે એ બધા વનવાસી રાજાઓને જીત્યા અને નાટાના સ્વામી પર પણ પોતાનું પ્રભુત્વ સ્થાપિત કર્યું. પછી, પુલિંદોને હરાવીને, તે દક્ષિણ તરફ આગળ વધ્યો. નકુલના નાના ભાઈ સહદેવે એક દિવસ માટે પાંડ્યના રાજા સાથે યુદ્ધ કર્યું. તેને પણ જીત્યા પછી, તે દક્ષિણ દિશામાં આગળ વધ્યો અને પ્રસિદ્ધ કિશ્કિંધા ગુફા પાસે પહોંચ્યો. એ સ્થાન પહેલાં વાનરરાજ વાલી દ્વારા, અને પછી રામભક્ત સુગ્રીવ દ્વારા રક્ષાયુક્ત હતું. સહદેવે ત્યાં પ્રવેશ કર્યો અને સુગ્રીવને પડકાર્યો. ત્યાં તેણે વાનરરાજ માઇંદ અને દ્વિવિદ સાથે સાત દિવસ સુધી યુદ્ધ કર્યું, પણ બંનેમાંથી કોઈ પણ પરાજય પામ્યો નહીં. અંતે એ બે મહાન આત્માવાળા વાનરોએ ખુશીથી સહદેવને કહ્યું: “હે પાંડવોમાં શિખર, તું બધા રત્નો લઈ જા; તારા ધર્મનિષ્ઠ યુધિષ્ઠિરના કાર્યમાં કોઈ અવરોધ ન આવે.” પછી સહદેવે રત્નો લઈને મહિષ્મતી શહેર ગયો, જ્યાં તેણે રાજા નીલ સાથે યુદ્ધ કર્યું. પાંડવોમાં શૂરવીર અને દુશ્મનવંશના વિનાશક સહદેવે એ યુદ્ધમાં ભાગ લીધો, જે ડરપોક લોકોને પણ ભયભીત કરી દે એવું હતું. એ યુદ્ધમાં દેવતાઓના હવનકુંડના વાહક અગ્નિદેવે સહદેવને મદદ કરી, દુશ્મનસેનાનું વિનાશ કર્યું અને લોકોના જીવને જોખમમાં મૂકી દીધા. એ સમયે સહદેવની સેના વચ્ચે રથ, ઘોડા, હાથી, માણસો અને તેમના કવચ—all અગ્નિથી પ્રજ્વલિત થવા લાગ્યા. આ દૃશ્ય જોઈને, કુરુવંશી જનમેજયનું મન ખૂબ ગભરાઈ ગયું અને તે જવાબ આપી શક્યો નહીં. બ્રાહ્મણો, એ યુદ્ધમાં સહદેવ યજ્ઞ માટે પ્રયત્નશીલ હતો ત્યારે અગ્નિદેવ શા માટે વિરોધી બન્યા, એ વાત જાણવા માંગે છે. મહિષ્મતી શહેરમાં, એક વખત અગ્નિદેવને પ્રેમી રૂપે પકડવામાં આવ્યા હતા. રાજા નીલની પુત્રી અતિ સુંદર હતી અને પોતાના પિતાની આરાધનામાં હંમેશાં અગ્નિહોત્ર કરતી. પંખાથી પવન આપતાં પણ એ અગ્નિ પ્રજ્વલિત થતો નહોતો, જ્યા સુધી કે એ યુવતીના મુગ્ધ કટોરાકાર હોઠોથી પવન ન ફૂંકાતો. પછી દેવત્વયુક્ત અગ્નિએ એ સુંદર યુવતીની ઇચ્છા કરી અને રાજા નીલે તેને નજીક લાવ્યા. ત્યારબાદ, બ્રાહ્મણરૂપે અગ્નિએ સંયોગવશે એ કમરપટલી, કમળનેત્ર યુવતી સાથે સહવાસ કર્યો; પણ ધર્મનિષ્ઠ રાજાએ શાસ્ત્રોક્ત રીતે તેને મનાઈ કરી. એથી ક્રોધિત થઈને અગ્નિદેવે જ્વલંત રૂપ ધારણ કર્યું; અને એ જોઈને આશ્ચર્યચકિત રાજાએ માથું ધરતી પર નમાવ્યું. થોડા સમય પછી, રાજાએ ફરીથી એ યુવતીને બ્રાહ્મણરૂપે આવેલા અગ્નિને આપી દીધી. એ રીતે રાજા નીલની ભ્રુકુટિવાળી સુંદર પુત્રી પ્રાપ્ત કરીને અગ્નિદેવ ખુશ થયા. પછી, હોળી સ્વીકારનાર અગ્નિએ રાજાને પસંદગીનો વરદાન આપ્યો; અને રાજાએ પોતાની સેનાની સુરક્ષા મેળવવાની ઇચ્છા વ્યક્ત કરી. એ સમયથી, કોઈ પણ રાજા અજ્ઞાનવશ એ શહેરને બળપૂર્વક જીતવાનો પ્રયત્ન કરે, તો અગ્નિ તેમને દહન કરી નાખે. અને મહિષ્મતીમાં, સ્ત્રીઓને બળાત્કારથી લઈ શકાય એમ ન હતું; માત્ર તેમની સંમતિથી જ શક્ય હતું. એ રીતે અગ્નિદેવે વરદાન આપ્યું કે એ શહેરમાં સ્ત્રીઓને બળપૂર્વક અપહરણ કરી શકાશે નહીં અને એ શહેરના રાજાઓ એ ઋણમાંથી મુક્ત થયા. તેથી, એ શહેરના રાજાઓ અગ્નિના ભયથી હંમેશાં નિયમપૂર્વક શાસન કરતાં. પરંતુ સહદેવ, ધર્મનિષ્ઠ આત્માવાળો, જ્યારે પોતાની સેના અગ્નિથી ઘેરાઈ અને ભયભીત થઈ ગઈ હતી, ત્યારે પણ અડગ રહ્યો; તેણે પાણી સ્પર્શ કરીને પવિત્ર થઈ, પછી અગ્નિદેવને સંબોધન કર્યું.