Keldor is at the Berserker Islands searching for somebody savage and strong enough to assist him in his conquests, and an old shaman shows him images of a beast that he will find in a town at west.
At Keldor's arrival at the town, it begins raining, so he accepts the hospitality of a cat-woman, but then he faces her jealous wolflike mate. Suddenly, the wolflike man is killed by Beast Man, the beast Keldor was seeking for.
Beast Man refuses Keldor's offer and they fight. Beast Man is about to bite Keldor's head off until servants of King Trinok, ruler of the Berserker Islands, submit him with tranquilizer darts. They intend to cook both Beast Man and Keldor as a meal for their king.
Keldor awakes at a cell next to Beast Man and convinces him to work together to escape. They defeat the guards, but since they don't know the place, they end where the fire to cook them is being lit. King Trinok orders to kill them, but Trinok's people aren't rivals for Keldor's magic and Beast Man's brute strength. Finally, Trinok himself enters the fray and Keldor kills him with just one burst of magic energy. Keldor and Beast Man run away while Trinok's vizier offers a reward for the heads of the king's murderers.
Keldor tells Beast Man that, with the king dead and everyone in the Berserker Islands hunting him, his options are leave and serve him or stay and die. Beast Man addresses Keldor as his master.