Well, someone was doing the conquering. The first governments must have arisen spontaneously somewhere in the world.
Quite true. In his works, Marvin Harris shows quite brilliantly the evolutionary processes which lead to the subjunction of people, as control became more and more tight and adherence to the ruler became less and less voluntary.
It's fairly clear that the first real states arose in response to the requirement for complex hydrological works to support agriculture. Dams, irrigation canals, etc. All the primary states arose in river valleys and lake districts. Once someone seizes control of the waterworks, he's got you by the proverbial throat. You have to let him be king or you die.
The didn't arise spontaneously as a governments, their evolution to a government probably required many generations. They began as nomads, pillaging and plundering agricultural communities. This evolved to something resembling the protection racket of modern organised crime (a primitive form of government itself) collecting tribute from such a community, and then finally to a governing, taxing relation. This (the Gumplowicsz-Opppenheimer theory) is a widely accepted explanation of the origin of the state. That social contract stuff is a lot of bunk. Governments grew out of aggression and plunder. Lawmaking and other activites typical of government can all be explained as motivated by a desire to maximise production of goods by the laboring subjects.