The story associated with the origin of Pataliputra is mentioned in the Kathasaritsagara. Once there lived a wise man named Bhojika. He had three daughters who were given in marriage to three brothers. Once there was a great feminine in the region and the three brothers deserted their wives.
The three sisters led a miserable life and one of them was pregnant. In due course, the pregnant woman gave birth to a son. The three women looked after the newborn.
Shiva and Goddess Parvati who were roaming through the sky happened to notice the three women and the baby. Goddess Parvati wanted to know about the baby. Shiva then said that the baby in his previous birth was an ardent devotee of him. He is born on the earth to reap the benefits of his austerities. His wife of previous birth has been born to King Mahendravarman of Patala and in this birth too she will be his wife.
That night the three women had a dream and in which Shiva asked them to name the baby as Putraka and every day when the baby wakes up a thousand gold coins will be found under his pillow.
The dream proved to be true and soon Putraka grew up to be a powerful king.
Putraka then performed several austerities and gave huge donations to people. Hearing about the donations, the three brothers who had abandoned their returned. They were welcomed back by the wives. Putraka was happy to find his relations.
But wicked men can never be changed and they planned to kill Putraka and usurp his wealth. They planned to kill him in a Durga temple but Putraka was able to convince his assassins with more wealth than offered by his relatives.
The three brothers who wished to usurp the wealth of Putraka were killed by the ministers of the court.
Putraka disillusioned and disgusted with his relations and ministers went to the forest. Here he found two sons of Asura Maya fighting over the wealth of their dead father.
The wealth were a pair of magical shoes with which the wearer can fly, a staff with which what ever is written turns out to be true and a vessel which provides the desired food.
Putraka was asked to solve the dispute. He said that whoever will win a running race will take possession of the three magical items. The two demons agreed and they started running. Putraka ceased the opportunity took the staff and vessel and put on the shoes and flew away.
Putraka then went to the kingdom of King Mahendravarman
Putraka wanted to see the princess and so he used his magical shoes to reach the chamber of the princess. The princess was first surprised to see a man in the palace. But she did not make any noise as she had love in her eye. They talked all night. Thus Putraka started visiting her every night.
Soon the guards discovered the visit of Putraka. The informed the king. Putraka was caught and brought before the king. The king decided to put him to death. But Putraka used his shoes to escape. He then went to the princess and both of them escaped from the palace.
Putraka then carried the princess to the banks of Ganga . Patali was impressed by the power of Putraka and asked him to create a city on the banks of Ganga . He then drew a well protected and prosperous city with the magical staff. The city was born immediately and Putraka became the king. The city that was created by Putraka and Patali came to be known as Pataliputra.