Nala-Damayanti story is mentioned in the Vana Parva (वन पर्व) under Nalopakhyana Parva ( नलोपाख्यान पर्व) of the Mahabharata.
After the Arjun went to Indra loka for learning Asthravidhya (अस्त्रविद्या), remaining pandavas were visited by Rishi Brihadshava (बृहदश्व).
Yudhishthira (युधिष्ठिर) told rishi that he is not well versed in playing game of dice, because of which he has lost everything and made his family suffered. Rishi Brihadshava told Yudhishthira not to become sad by his suffering and his limited knowledge of game of dice. Rishi promised that he will teach the game of dice to Yudhishthira and also narrated a story about King Nala who similarly suffered after losing everything to his brother in the game of the dice.
Lord Krishna while mentioning the ill-effects of gambling to pandavas mentioned about King Nala who was dethroned from his kingdom, because he lost everything in game of dice. ( Mahabharata Vana Parva 13.5)
Nala-Damayanti (नल-दमयन्ती) story begins –
Nala, King of Nishadha (निषेध) , was born to Veersena. At that time there was another kingdom called as Vidarbha (विदर्भ) which was ruled by King Bhim, who has 3 sons named as Dam, Danta, Daman and a daughter named as Damayanti .
Once Nala was sitting in a park where he found a beautiful swan. The swan told him about Damayanti . An impressed Nala told the swan to go to Damayanti and tell her about him. Damayanti on listening from swan about the King Nala got attached to him and decided to marry him.
Soon King Bhim organised the swayamvar (स्वयंवर) for her daughter
Damayanti and invited various kings. Dayamanti was so beautiful that listening about her swayamvar (स्वयंवर) from Rishi Narada, other devatas such as Lord Indra, Varuna, Agni Dev and Lord Yama went to marry her in the swayamvar, but Damayanti only choose King Nala as her husband.
All the devata’s left the place praising the qualities of Nala and blessing the couple. Kali Yuga (कलियुग) also has this desire to marry Damayanti , so when he was going towards the Vidarbha , he was met by Lord Indra and other devatas who told him that Damayanti is already married to King Nala. Upset over this Kali decided to take revenge from the King Nala. He vowed to divert Nala from the path of dharma and to separate Nala and Damayanti.
Kaliyuga (कलियुग) waited for 12 years before he can entered in the body of King Nala and distort his mind. Kaliyuga also entered in the body of Pushkar (पुष्कर ) who was younger brother of King Nala, and made him to ask King Nala for a game of dice.
Being influenced by evil, Nala agrees to play game of dice with his brother Pushkara who took away all his wealth and the kingdom. Pushkar than made him to leave the Nishedha Kingdom.
Soon Damayanti and King Nala found themselves in the forest, and their suffering started. While Damayanti was sleeping, Nala under the influence of Kali, deserted her and went away.
Parted from Damayanti , Nala saw a Karkotaka Naga (कर्कोटक नाग) who was burning in a fire due a curse and saved him. The Karkotaka Naga used poison to transform Nala into an black ugly man and he advised Nala to serve King Rituparn (ॠतुपर्ण) of Ayodha kingdom, as his charioteer. Nala also changed his name as Bahuka (बाहुक). Since King Rituparn is well versed in game of dice, so Nala should learn that knowledge from him and in return should teach him charioteer skills.
Meanwhile Damayanti when found that Nala has deserted her, soon she started looking for him. While going through the forest she faced the snake, Hunter (व्याध) whom she burned down, met rishi’s who comforted her, met merchant travelers who were killed by the herd of wild elephants, she than finally reached to the kingdom of Chediraj and met Queen Bhanumati, and then finally found by her father, she returned to Vidarbha kingdom. On reaching Vidarbha she declared a reward for anyone who would find her husband. One of her scouts returned and told her about a charioteer named Bahuka in Ayodha kingdom.
Damayanti sent a misleading message to King Rituparn that she is having a second swayamvar only to make it heard by King Nala ( Bahuka). On hearing that Damayanti was going to marry another husband, Bahuka drove King Rituparn towards Vidarbha . During the journey, Kali (कलि) came out of the Nala’s body and asked for forgiveness for fear of being cursed. Nala forgave him. Damayanti when found out that King Rituparn and the charioteer named Bahuka has arrived, she sent her servant named Keshini (केशिनी) to test Bahuka. Keshini found out that Bahuka is indeed King Nala and took her to near to Damayanti . Both recognized each other and Nala got his original beautiful form.
Learning Rituparn’s skills at dice , Nala exchanged his skill as a charioteer . Then he set out to regain his kingdom from his brother. Reaching Nishadha (निषेध), he challenged Pushkara for a match of dice and with his new learning he won back his kingdom and power.