Most likely an organised version started around the time of the first town and cities (say 5000 BCE +/- 1000yrs) when people started to identify with their town/ city.
Before that you would have had skirmishes between tribes.
When the people living in the cities began to create surplus of resources the wandering people may have been motivated to take these resources by infiltration, robbery and murder; rather than brute force.
If this takes a week or two of coverte action, bam! You have your first terrorist.
™ Version 4.2