While The Empire stretches across a vast amount of real estate, there is a kingdom that stretches across the mountains to the east of The Empire that has retained it's independence. This is the Kingdom of the Giants.
The Giants have a King, and being King means you have one job to do, but a difficult one nonetheless. The Giant King has to keep the Giants from killing each other. The giants are composed of several tribes, who even among each other in their own tribes have quarrels.
The great Giant King is the strongest Giant, and at any time another Giant can come and challenge the King to a fight. If the King ever looses, his defeater become King.
Life in The Kingdom
Giants are unintelligent, not very adventurous, and very territorial creatures. They are satisfied with simple lives, and simple, though generally violent games, and as such get into many scuffs and quarrels with each other, even over simple things like who won a insignificant game. No Giant tribe has ever gone to war with another, but individuals have quarrels often.
Annexation by The Empire
While being formed, The Empire, led by Arcturus Mengsk, attempted to ally with the giants. It did not go well. The emissaries along with their parties were destroyed, or sent back with their tail between their legs. Arcturus decided that there would be no allying with the Giants as they are barely allied with each other. While killing them was an option to make sure that they, who lived so close to The Empire, would not one day turn on The Empire and cause them to fight a two-front war at perhaps an inopportune moment, Mengsk took another route. He Instead attempted to Annex their kingdom, to add their strength to The Empire's.
He hatched a plan to invade their lands, hoping it would unite the Giants against a common enemy. Their goal was to cause the Giants to declare war so the King would come out and fight. He was right - they united and fought against The Empire. The Empire would of lost if their goal was to defeat all the giants and take their lands. The Giants needed no siege artillery, they would hurl great stones at The Empire's forces, and many many people died before even a Giant was in sight. After a campaign that lasted through three Emperors, the plan eventually worked and the King came out. He brought many a Giant to bear, and his defeat occurred during a terrible and brutal battle under emperor Valerian.
As the King was lying on the ground defeated, Valerian personally came up to him and said to him, "I have defeated you, by right I am King now." The Giant King looked at him through a broken eye-socket bone. Valerian continued, "But I renounce that right good King. This is after all your people's land." The Empire's clerics did their good work and healed the Giant King and he rose up to one knee to bend down to look at the tiny emperor. Valerian looked at him in the eye and said, "Can we talk now, or do I have to give you another beating?" The Giant King and gave a hearty laugh and responded, "Let us talk, maybe puny humans not so puny after all."
Knowing that any deal that appeared to have the Giants as slaves, or defeated enemies would be tenuous at best, Valerian skillfully crafted a deal that looked more like a trade agreement than a terms of defeat.
The deal created a trade route between the two kingdoms. Since the Giants insisted that the humans don't go into their lands, and of course the Giants had no interest in traveling to any of the lands of The Empire, a town was to be established in the area between the two kingdoms that would have both humans and Giants working together and would serve as the base where all trading was done. The goods traded to The Empire was some lumber and stones and some metals, but those were all to disguise the good that Valerian really wanted from the Giants: soldiers. The Giants were to send some of their own to fight in The Empire's wars.
The war was a success, and The Empire became the first nation to ever ally with the Giants. Now they have new weapons to bear against the Orcs - living, breathing, behemoth-sized weapons.