Krishna is of immense service to the people of Mathura, for very soon after his arrival there, Jarasandha, Kansa's father-in-law, attacks them, and is beaten eighteen times by his prowess. When the people were almost exhausted with these protracted struggles, a new enemy appears in Kalayavana, King of the Yavanas, who wish to try their strength with the Yadavas under Krishna. He, thinking that by a struggle with two foes at once the people would be exhausted, provided a new city, so strong that women could protect it, to which he conducted the inhabitants of Mathura. No sooner had he made the people secure than he went forth unarmed and alone, and attracted the attention of the King of the Yavanas, whose army still surrounded the city. Krishna, seeing the king was following him, entered a cave, and concealed himself; the king seeing a man lying at its entrance, thinking it must be Krishna, kicked it, and in an instant became a heap of ashes. The secret of his destruction was this: a man named Muchukunda had received as a boon from the gods the power to sleep for a long period, with this condition, that whoever awoke him should be instantly consumed by fire emanating from his body. Unwittingly the King of the Yavanas kicked him and received the penalty of his ignorance; whilst Krishna escaped, and seized the army and treasures left without an owner.

Amongst many others, Krishna fell in love with Rukmini, the daughter of Bhismaka, King of Vidhabha (Berar); but her brother Rukmin hated him, and refusing to give his consent, at the advice of Jarasandha, she was betrothed to Sisupala. This Sisupala was no other than Hiranyakasipu and Ravana, whom in previous incarnations Vishnu had slain. On the eve of the wedding Krishna carries off Rukmini, leaving Balarama and his friends to take care of themselves; and when Rukmin follows him with an immense army, Krishna easily destroys his companions, and, but for the intercession of Rukmini, would have killed his brother-in-law too. This Rukmini was none other than Lakshmi, Sita and others, who, in her earlier incarnations, had stood in a similar relationship to him.