મહાભારતની આ પવિત્ર કથા અનુસાર, સહદેવે યજ્ઞ માટે અગ્નિદેવની આરાધના શરૂ કરી. તેણે વિનમ્રતાપૂર્વક આગ્રહપૂર્વક કહ્યું: "હે અગ્રણી અગ્નિદેવ, આ ઉપક્રમ તમારાં માટે જ છે. કૃષ્ણના માર્ગે ચાલનારા, દેવતાઓના મુખ સ્વરૂપ, હવન સ્વરૂપ પાવક, તમને વંદન છે." સહદેવએ અગ્નિના વિવિધ નામો અને ગુણોનું સ્મરણ કર્યું—"તમે પાવક છો, કેમ કે તમે પવિત્રતા લાવો છો; હવ્યવાહન છો, કેમ કે તમે હવનને દેવતાઓ સુધી પહોંચાડો છો; વેદો પણ તમારાં માટે જ પ્રગટ થયા છે, તેથી જાતવેદા કહેવાય છો." પછી તેણે આગળ કહ્યું: "તમે ચિત્રભાનુ, દેવતાઓના સ્વામી, અનલ, વિભાવસુ છો. તમે સ્વર્ગના દ્વારોને સ્પર્શો છો, હુતાશ, જ્વલન, શિખી પણ તમે જ છો. વૈશ્વાનર, પિંગેશ, તેજસ્વી પલવંગ, અને કુમારના પુત્ર, રુદ્રના અંશ, સુવર્ણ-સ્વરૂપ પણ તમે જ છો." સહદેવે પ્રાર્થના કરી: "મને અગ્નિથી શક્તિ, વાયુથી શ્વાસ, પૃથ્વીથી બળ અને જળોથી કલ્યાણ પ્રાપ્ત થાય." તેણે અગ્નિને 'જલનો અંશ, મહાત્મા, જાતવેદા, દેવતાઓના સ્વામી, દેવમુખ' કહીને સત્યથી પવિત્ર થવાની વિનંતી કરી. સહદેવએ કહ્યું: "મુનિઓ, બ્રાહ્મણો, દેવતાઓ અને અસુરો પણ હંમેશા તને યજ્ઞમાં શ્રદ્ધાપૂર્વક અર્પણ કરે છે—મને પણ સત્યથી પવિત્ર કરો." "તમે ધૂમકેતુ, શિખી, પાપનાશક, અજન્મા છો; તમે સર્વ જીવોમાં સદા નિવાસ કરો છો—મને સત્યથી પવિત્ર કરો." અંતે સહદેવે અતિ શ્રદ્ધાથી પ્રાર્થના કરી: "હે પ્રકાશમાન અગ્નિદેવ, મેં તમારી સ્તુતિ કરી છે—મને સંતોષ, પોષણ, વિદ્યા અને આનંદ આપો." પછી શાસ્ત્રોક્ત રીતે જણાવાયું કે, જે કોઈ આ અગ્નિ મંત્રનું પઠન અને હવન કરે છે, તે સંયમી અને સુખી બની, સર્વ પાપોથી મુક્ત થાય છે. પછી સહદેવે અગ્નિને વિનંતી કરી: "હે હવ્યવાહન, યજ્ઞમાં વિઘ્ન ન લાવશો." આ કહ્યા પછી, માદ્રીપુત્ર સહદેવે કૂશના આસન પાથર્યા. વિધિ અનુસાર, પોતાની સેના સામે, સહદેવ પાવક પાસે ગયો—યद्यપિ તે થોડી ભયભીત અને ચિંતિત હતો. પરંતુ અગ્નિએ તેને દહન કર્યો નહીં. એ સમયે મહાસાગરે સહદેવને સંબોધીને કહ્યું. પછી અગ્નિદેવ સહદેવ પાસે ધીમે અને શાંત સ્વરે બોલ્યા: "ઉઠ, ઉઠ, હે કૌરવ્ય, મેં તારી પરિક્ષા લીધી છે. હું તારા તેમજ ધર્મપુત્રના મનના ભાવ જાણું છું, પણ મને આ શહેરની રક્ષા કરવી છે." "જ્યારે સુધી રાજા નીલની વંશ પરંપરા ચાલુ રહેશે, તું જે ઈચ્છે છે, તે હું પૂરૂં કરીશ, હે પાંડવ." આ વાતથી આનંદિત થઈ, સહદેવે હાથ જોડીને, નમ્રતાપૂર્વક પાવકની પૂજા કરી. પછી પાવક દૃશ્યમાંથી અદૃશ્ય થયા. રાજા નીલ આગળ આવ્યા અને પાવકના આદેશથી સહદેવનું સન્માન કર્યું. સહદેવે પણ એ આદરપૂર્વક સ્વીકાર્યું અને હસ્તગત કર્યું. આ પછી વિજયી સહદેવ દક્ષિણ દિશામાં આગળ વધ્યો. તેણે ત્રિપુરા અને તેના શક્તિશાળી રાજાને જીત્યા. પછી તેણે મહાન પુરુષાર્થથી ઋષિ કૌશિક સમાન રૂપ ધરાવતા પૌરવોના રાજાને પણ વશમાં કર્યો. પછી તેણે સૌરાષ્ટ્રના રાજાને પોતાના વશમાં કર્યો અને સૌરાષ્ટ્ર પ્રદેશમાં વસતા રુક્મિ ને સંદેશ મોકલ્યો. તેણે ભોજકટા ખાતે નિવાસ કરતા વિદ્વાન, ધર્મનિષ્ઠ અને ઈન્દ્રમિત્ર ભીષ્મક રાજાને પણ સંદેશ મોકલ્યો. ભીષ્મક અને તેના પુત્રએ કૃષ્ણનું માન રાખીને સહદેવની આજ્ઞા સ્વીકારી. પછી સહદેવ, રત્ન સ્વીકારી, આગળ વધ્યો અને શૂર્પારક, તાલકાટા વગેરેને પણ જીત્યા. દંડક અને વિદેશી દ્વીપવાસી રાજાઓને પોતાના વશમાં લીધા. નિષાદ, પુરુષાદ, કર્ણપ્રવરણ, કાલમુખ (માનવ અને રાક્ષસ વંશના) એ બધાને જીત્યા. કોલગિરિ, સુરભિપટ્ટન, તામ્રદ્વીપ, રામક પર્વત—આ બધાને પણ પોતાના અધિકાર હેઠળ લાવ્યા. ટિમિંગિલ રાજા, એકપાદવાળા લોકો, કેરલવાસીઓ અને જંગલવાસીઓને પણ જીત્યા. સહદેવે સંજયંતી, પશાંડ, કરહાટક શહેરોને દૂત દ્વારા પોતાના વશમાં કરીને તેમને કર ચૂકવવા ફરમાવ્યા. પાંડ્ય, દ્રવિડ, ઓદ્ર-કેરલ, આંધ્ર, તાવન, કલિંગ અને ઉષ્ટ્રકર્ણિક—આ બધાને પણ જીત્યા. અટવી અને યવન શહેરને પણ દૂત દ્વારા પોતાના અધિકાર હેઠળ લાવ્યા અને તેમને કર ચૂકવાવ્યા. ત્યારબાદ તે તામ્રપર્ણી નદી પાર કરી, પવિત્ર કન્યાકુમારી સ્થળે પહોંચ્યો. દક્ષિણ પ્રદેશને સંપૂર્ણ રીતે જીત્યા પછી કુરુપુત્ર સહદેવ આગળ વધ્યો. પછી, સમુદ્રના ઉત્તરી તટે પહોંચીને, સહદેવે પોતાના ભત્રીજા ઘટોત્કચનું સ્મરણ કર્યું. તરત જ, ઘટોત્કચ—મેરુ પર્વત સમાન ભવ્ય—ત્યાં આવી પહોંચ્યો. ભૃગુકચ્છથી ધર્મરાજના આદેશ અનુસાર, દુશ્મનોના સંહારક અને વિદ્વાન સહદેવે કહ્યું: "તેને બોલાવો." રાક્ષસોથી ઘેરાયેલા ઘટોત્કચએ સહદેવ પાસે આવી, ભયાનક રૂપ ધરાવતા મહાત્મા ઘટોત્કચને નમસ્કાર કર્યા. પછી, સહદેવે ત્યાં ઊભા રહી, પ્રેમભરી રીતે મહાન આત્મા પૌલસ્ત્ય, મહાનુભાવી વિભીષણને સંદેશ મોકલ્યો. વિભીષણે પણ આનંદપૂર્વક આ આજ્ઞા સ્વીકારી અને તેને કૃષ્ણની આજ્ઞા સમજી માન આપ્યો. પછી તેણે વિવિધ રત્નો, ચંદન, અગર અને દૈવી ભુષણો સહદેવને મોકલ્યા. આ રીતે સહદેવે અગ્નિદેવની કૃપાથી અને પોતાના પરાક્રમથી દક્ષિણ દિશાના અنےકો રાજાઓને જીત્યા, મહાન યશ પ્રાપ્ત કર્યો, અને યજ્ઞ માટે સર્વત્ર વિજય યાત્રા કરી.