Wikipedia's article on the subject estimates that the practice could have existed during the Bronze Age and possibly earlier.
The practice of declaring war has a long history. The ancient Sumerian Epic of Gilgamesh gives an account of it, as does the Old Testament.
However, the practice of declaring war was not always strictly followed. In his study Hostilities without Declaration of War (1883), the British scholar John Frederick Maurice showed that between 1700 and 1870 war was declared in only 10 cases, while in another 107 cases war was waged without such declaration (these figures include only wars waged in Europe and between European states and the United States, not including colonial wars in Africa and Asia).
It is unknown when the practice became the norm. The wiki notes in an offhand manner that notions of chivalry and fairness might have been one of the motives behind the tradition.
The utility of formal declarations of war has always been questioned, either as sentimental remnants of a long-gone age of chivalry or as imprudent warnings to the enemy. For example, writing in 1737, Cornelius van Bynkershoek judged that "nations and princes endowed with some pride are not generally willing to wage war without a previous declaration, for they wish by an open attack to render victory more honourable and glorious." Writing in 1880, William Edward Hall judged that "any sort of previous declaration therefore is an empty formality unless the enemy must be given time and opportunity to put himself in a state of defence, and it is needless to say that no one asserts such a quixotism to be obligatory."
One of the cited sources for a lot of the information on this wiki is The Lost Art of Declaring War By Brien Hallett. In it, Hallett provides other compelling reasons why declarations of war existed:
Until roughly the seventeenth century, initiating war involved elaborate, complex, and lengthy formalities that were cloaked in religious formulas and legalistic jargon. Nonetheless, hiding beneath these sacred rites and judicial forms were exceedingly pragmatic political and diplomatic processes in which the formal declaration of war was an integral and crucial element. Politically the rites for declaring war usually required extensive public debate in governing forums that culminated in the writing of a fully reasoned declaration of war. The practical reality sustaining these public debates was the fact that war chiefs held relatively little political power and therefore had to defer to the council of elders, the assembly, the senate, or the great council before they could take up their spears. Diplomatically these ceremonies involved dispatching a special emissary to the potential adversary empowered to negotiate over the grievances and remedies articulated in the formal declaration that the emissary carried. The practical reality undergirding this negotiating mission was the essential autonomy of each tribe, city, or kingdom, on the one hand, and the difficulties in transportation and communication, on the other hand, which made contacts between potential adversaries sporadic. Indeed, war was for all practical purposes the only question important enough to force diplomats to break this isolation and risk the dangers of traveling to distant lands.
As the seventeenth century approached, however, both the political and diplomatic realities changed remarkably. Improvements in transportation and communications led to the development of permanent diplomatic representation in foreign courts and hence to continuous interchanges between monarchs.
Hallett goes on to state that the rise of ambassadors in foreign courts and improved communication streamlined this complex process considerably.
