Whereas the King has the supreme power over the Legion, Commanders act in their stead, and are thus in charge of both the ground and air-forces.
At some point in time, captain Tah'vraay of "The Father's Bones" set the King's granaries on fire, yet she made some sort of a non-aggression pact with commander Temmet Aelloon. According to Tah'vraay the King owes a debt to her crew.
Commander Aelloon used his forces to make Benn'joon repay a debt she had to him, tracking her down to the tavern of Nestorep. As she was unable to pay he suggested to instead end her life, but she summoned forth Cale'anon - and with him, Sooba, and Richard's help, she managed to flee the commander. He sent a whole wing after her, but she eventually got away. Unknown to Aelloon Benn'joon's new companions decided to go find the Sword of Truth, so that she could pay back her debt.
However, Aelloon and his Legion army continued to search for Benn'joon and her group of friends, even when they hired captain Tah'vraay to sail them across the ocean to the Ketten Wastelands, sending a warship after Tah'vraay's "Bones". However, with the combined powers of Krunch's pure strength and Richard's magic, the Legion warship was sunk.