Kull, King of Valusia attends a royal wedding of the heiress of Thule to the crown-prince of Verulia. At some point Ku-Var the ruler of Atlantis enters the room. Kull is amazed by his chief guard, a fierce woman named Iraina, who is dressed in an impressive outfit made of tiger skin.
Following the wedding a series of contests is held. The king of Thule calls for Kull and Ku-Var to choose two of their best fighters to face each other in combat. Ku-Var picks Iraina and Kull chooses his Pictish guard Brule. Brule refuses to battle a woman, but Iraina's taunts frustrate him so he attacks her but he loses.
Time passes until one day an old Atlantean mentor of Kull's, Ram-Os, seeks him out and warns him that Iraina has killed Ku-Var and now leads an army of women bent on conquering the world!