Caveman "Thag" organized his clan to fight against the barbaric clan of "Zhug" just beyond the mountains. Apparently, the two got it on when Zhug accused Thag of plagerising his cave paintings.
They were actually called "Og" and "Ug", and were fighting over the possession of Cave 632 (you know, the one on the Eastern side of the mountain, just above the small beach by that sea...) and the priceless woman who lived there, Cher.
To answer your question, the first recorded war happened in Mesopotamia, as has already been pointed out, between Sumer (who were most probably invaders) and Elam, and took place around modern-day Basra. Eerie, eh?
http://ancienthistory.about.com/b/a/005034.htm
For more on the conflict:
http://www.au.af.mil/au/awc/awcgate/gabrmetz/gabr0004.htm