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