On the one hand, the proposition is kind of obvious and self-evident - "I'll trade you ${thing you want} for ${thing I want}" is the next step from "I'll beat you up and take ${thing I want} from you", and then basic money is just doing the trade in two steps. On the other hand, single-step trading - that is, barter - gets infeasible as the primary trading model
very quickly. Not because of specialization (the "I want to trade shoes for food, but everyone already has enough shoes" problem), but because of
fairness - everyone's memory and the "shared knowledge" established through gossip can scale only so far, and past that point, you need some other means to ensure exchange of goods and services stays balanced over time (and that your group can agree fair balance is being maintained).
Basically, either your proto-society develops ways to track balance of trade[0], or it'll grow a freeloader problem, which will keep it down and possibly even destroy the group. That point comes early enough that it's entirely likely the early societies that didn't develop money didn't grow large enough, and didn't survive long enough, to enter historical record.
--
[0] - Trading via a medium of exchange - that is, some form of money - is just one way to achieve it, but it has the useful property of being self-balancing, thus not requiring shared global state. That is, you don't have to keep official logs of every trade made by everyone in your group to keep things fair and balanced (or even define, update and defend what "fair" and "balanced" means, which is something everyone has slightly different view of) - you can just establish a common medium of exchange, give people freedom to individually negotiate the exchange rates, and you have a self-balancing system.