Markets are ~10,000+ years older than libertarians. Some early examples had people swapping from banditry to trade depending on how well armed the people they encountered where. No outside forces nessisarily, but no rule of law either.
Sure markets may be older than libertarians, but even though libertarians didn't exist to enunciate libertarian theory back then, the fundamental libertarian phenomenon of non-aggression and voluntary exchange as you mention was indeed present.
But most non-libertarians believe in non-aggression and voluntary exchange too. They just argue that some taxes aren't aggression and some exchanges aren't really voluntary.
These where often rather agressive trades, even without violence actually occurring it's threat was still on the table.