Religion has been used by all groups of peoples to help them understand and regulate warfare and thus also to convince people to take part (recruit them). Provided here is a Wikipedia list of war gods. In a monotheistic religion, the role of the war god is combined as a trait of the one god. In the Old Testament, the Jewish God can be seen commanding his people to go to war to defeat peoples who commit grave sins. In other religions, the people might take captives to use as human sacrifice, such as the pre Buddhist deity Dayisum Tngri. Burial of slaves, often war captives, at a master's death was a common form of human sacrifice in other cultures.
The Nuristani people are a very old culture. They are mentioned in the Rigveda, one of the world's oldest manuscripts, composed in 1500-1200BCE. Their war god is Great Gish. After an enemy is killed in battle, a victory dance is given to Great Gish. This type of religious ritual would have been common among tribes without writing systems, as well, so it is impossible to know which peoples did this first.