राजा भीम ने इस बात पर खूब अच्छी तरह से विचार किया। उसने अनुभव किया कि दमयन्ती अब विवाह के योग्य हो गई है और उसका प्रबन्ध जल्दी ही होना चाहिए। लेकिन उसे उसके लिए कोई योग्य वर नहीं दिखाई दे रहा था। तब उसने सोचा कि दमयन्ती का स्वयंवर रचाया जाये। उसमें आने वाले विवाह के इच्छुक लोगों में से कन्या स्वयं अपना वर चुन लेती है।

उसने स्वयंवर की तारीख निश्चित कर दी। बहुत से राजाओं और राज- कुमारों को निमन्त्रित किया गया। उनसे अनुरोध किया गया कि वे इस समारोह में आयें जिससे उसकी पुत्री उनमें से किसी एक को अपना पति चुन सके। दमयन्ती दुनिया में सबसे सुन्दर लड़की है, यह सुकीर्ति दूर-दूर तक फैल चुकी थी। सभी राजाओं और राजकुमारों ने निमन्त्रण स्वीकार कर लिये । जल्दी ही वे सब लोग विदर्भ की ओर रवाना हो गये। नल को पूर्ण विश्वास था कि वह दमयन्ती को अपनी बनाने में सफल होगा। वह भी अपने रथ में सवार हो स्वयंवर के लिए चल पड़ा। इसी समय घुमक्कड़ मुनि नारद स्वर्ग में पहुँचे और देवताओं से मिले । उन्होंने उनसे पृथ्वी के सब समाचार जानने चाहे।

"केवल एक ही समाचार है|" नारद ने उत्तर दिया, "सब राजा और राजकुमार दमयन्ती के स्वयंवर के लिए जो जल्दी होने वाला है, उत्सुक हैं।" 

"इतनी उत्सुकता का कारण क्या है?" स्वर्ग के राजा इन्द्र ने पूछा, "राजा भीम की पुत्री दमयन्ती बहुत ही सुन्दर है। सब राजा और राजकुमार स्वयंवर में जाकर उससे विवाह करने के इच्छुक हैं।" 

''यदि वह इतनी ही सुन्दर है," इन्द्र ने कहा, "तो मेरे विचार में उस लड़की का विवाह किसी एक देवता से होना चाहिए।"

"हाँ, हाँ, चलो चल कर हम भी अपना भाग्य आजमायें," दूसरे देवता अग्नि (आग का देवता), वरुण (जल का देवता), और यम (मृत्यु का देवता) एक साथ बोल उठे। 

देवराज इन्द्र भी इससे सहमत थे। बस चारों देवता दमयन्ती के स्वयंवर के लिए चल पड़े। देवता जब पृथ्वी पर पहुंचे और विदर्भ की ओर जा रहे थे तो रास्ते में उन्हें नल मिला। उन्होंने उसका रथ रोककर उसे बताया कि वे कौन हैं और फिर उससे उनका एक सन्देश ले जाने के लिए कहा। नल ने देवताओं को प्रणाम किया और वायदा किया कि वह उनके आदेश का पालन करेगा।

"हम दमयन्ती के स्वयंवर में जा रहे हैं और हम चाहते हैं कि वह हम में से किसी एक को वरे। हमारा यह सन्देश लेकर तुम दमयन्ती के पास जाओ।" उनका आशय जानकर नल ठगा-सा देखता रह गया। उसने हाथ जोड़कर कहा, “मैं भी स्वयंवर में जा रहा हूँ। मेरी समझ में नहीं आ रहा कि आपकी इच्छा कैसे पूरी करूँ।"

"तुमने हमारे कहे के अनुसार ही करने का वायदा किया था,” इन्द्र ने कहा, “अब तुम अपने वायदे से पीछे कैसे हट सकते हो।" 

नल बहुत दुखी था। वह देवताओं का सन्देश नहीं ले जाना चाहता था। उसने कहा, “मैं राजा भीम के महल में कैसे जा सकूँगा-वहाँ पर तो कड़ा पहरा रहता है ? और फिर मैं दमयन्ती से भी कैसे मिलूंगा। उसके पास दूसरी स्त्रियाँ होंगी?"

"हम तुम्हें अदृश्य हो जाने की शक्ति देते हैं|" देवराज इन्द्र बोले, "दमयन्ती के सिवाय तुम्हें कोई दूसरा नहीं देख सकेगा। अब उसके पास जाकर हमारा सन्देश दो और फिर उसका उत्तर लेकर वापिस आयो।"