Admitting that a story which has been around for long is wrong is not an easy task. Yet, it is one of those stories for which the counter argument actually makes much more sense than the original. The first time I saw the argument about barter never taking place in primitive societies was when going through the Chicago Plan (a nice refutation of which can be found here). Although this made some sense, I could not really claim full understanding of the whole issue until I read David Graeber's "Debt: The First 5,000 Years" (and a book review of which I hope to write soon).
The book's argument on barter can be summarized in the following: In small, prehistoric societies, barter never existed; there are no anthropological evidence to support this theory. In fact, credit (even though not in the way we understand it now) was the only way through which activities were taking place in such societies. A simple way to understand how this makes sense is by imagining that the only people in the world are you, 3 of your best friends and your spouses, a total of 8. Now, let's say that one of your friends is good in setting traps, the other is a great gatherer, you are a great hunter and the last is an amazing farmer. At the end of the day, each of you will have collected some amount of food, be it large or small. If your gatherer friend had just a small amount of food would you let him starve to death because on a single day he could not have come up with enough food?
The answer here is no. First of all, you are friends and friends don't let each other die of hunger. Second, you need a gatherer in the group just in case everyone else has trouble finding food; even though your friend might not die tonight, starved people are more prone to diseases and other ills. Then, you need the extra person just in case some beasts attack you, or in case someone else is sick. Therefore, it is against both your personal as well as societal interest to let your friend starve. If you are going to offer your food to the other members of your group, and reciprocity is innuendo here, then there is no point in employing any source of measurement for what you offer. In two day's time, you will not wonder whether the meat you offered your friend was more than the grapes and apples offered in return. Just having them at the time is much more important.
What should be the juice of the above paragraph is that money has no place in a small society, where everyone knows everyone. Money only arises when we have to deal with strangers, whose ability to reciprocate we cannot know of. Still, it might have been easy to propose a rather complicated system of goods with equal value, for example, a chicken worth 3 kilograms of sugar or 4 kilograms of flour, just like Mesopotamians used to do.
Yet, the use credit was much easier than the use of any kind of money. I owe you 2 chicken, you some other person 3 kilograms of rice and so on. In ancient times, debts was the currency in circulation not money. The reason might have been just that money has to be something that everyone can use and accept or that money by John (i.e. credit) might not be accepted by Jill if she believes he is not creditworthy (obviously, some collateral was to be placed in case the person offered the loan could not repay: even people were at times traded in exchange for debt write-offs).
Enter the state. Imagine a sovereign ruler, so powerful that some consider him to be a deity. Nothing is now easier than the use of this power as a means of generating profit to fund a war or any other construction within his empire. Creating money was simply taking an amount of gold, stamping the face of the ruler and then giving it for payment to soldiers or anyone else who deserves payment for a price much higher than the what it cost to manufacture it. Why gold or silver and not anything else one might ask. The answer lies in (albeit denounced by Graeber) Paul Samuelson: it is simply because they are useless in any other form than creating pretty (and expensive) objects. Having copper as a metal during those times would have been an incentive for someone to use them to build arms or anything else if he could get them cheap enough. Gold would not offer the same incentives.
The reason for creating money is, as the book states, the facilitation of both trade and state transactions. Offering the state's guarantee on something has a much greater bearing than that offered by John or Jill and creating a market is easier when money is employed than when it is not. In essence, you need states (or at least some sort of regulator) for markets to exist. (For an argument against fully free markets Graeber points out to the situation after the fall of the USSR in the 1990's and the chaos which followed.)
In brief, the story is this: barter did not exist in the way usually portrayed by economics textbooks and money did not evolve as a consequence of bartering (i.e. people exchanging goods with others and having trouble keeping up with accounts). Barter was non-existent in prehistoric times and credit arose much before money did. Markets are in fact heavily reliant on money and money is non-existent without the state. Recent experience with Bitcoin also shows the same; without any backing from a state or any regulations behind it, it is evolving into a commodity rather than a means of transaction.