Kalayavana was a powerful king who ruled the region around present day Afghanistan when the avatar of Sri Krishna was present on earth. Jarasandha, who was constantly attacking Mathura , had taken the help of Kalayavana to defeat Sri Krishna. The story of the birth of Kalayavana is found in the Vishnu Purana and explains why Sri Krishna was not able to kill him in a combat.
Legend has it that Garga Rishi, an important Sage and head priest of the Yadava dynasty, was once ridiculed by the Yadavas as belonging to the third sex. Garga Rishi did not take the slight lightly and was infuriated by the laughter of the Yadavas. The angry sage took a vow to beget a son who would terrorize the Yadavas.
The Rishi then married a yavana princess and got a son who was named Kalayavana. The son then got a boon from Shiva that Yadavas will be afraid of him and they will not be able to defeat him.
Kalayavana then attacked the Yadavas and defeated them. Sri Krishna then took the help of King Muchukunda to annihilate Kalayavana.
Related
Story of Sri Krishna and Muchukunda