This is Adam Smith's just-so story, but he was wrong - no society has ever been shown to survive on a barter economy. Anthropologists have shown that what existed before trade was the same as what exists today when trade collapses: informally held debt. Alice knows how to work leather, Bob knows how to work wood; Bob needs a pair of shoes; Alice gives Bob a pair of shoes to satisfy his need and both Alice and Bob remember that; later, when Alice's house needs repairs she knows whose shoulder to tap on.
This is "barter" in the sense that Alice's and Bob's services have been transacted through time, but you'd be moving the goalposts since you just defined barter as Alice and Bob sitting down and determining precisely how much wood-labour equates to a fixed quantity of leather-labour at the point of purchase.
If you'd like to learn more, then David Graeber's book Debt: The First 5,000 Years, is something of a standard reference on the subject. It's on the Internet Archive.