Libertarian has a complicated history, since the uses of the term to designate proponents of free will are not entirely separate from those associated with anarchism and small-government philosophies. But we generally date the political use of the term to the French communist anarchist Joseph Déjacque's 1857 essay "De l'être-humain mâle et femelle," a response to some of Pierre-Joseph Proudhon's anti-feminist writings, in which Déjacque accused Proudhon of being an "Anarchiste juste-milieu, libéral et non LIBERTAIRE" (a phrase probably best rendered as "half-hearted anarchist, liberal and [not] libertarian.")

Déjacque then published a newspaper, Le Libertaire, between 1858 and 1861, while in exile in the United States. He was also involved in some organizational precursors to the First International. He work was largely forgotten for some time, but as anarchism (another term he pioneered) became the focus for a new movement, after the split in the International, anarchists began to establish a history for their tradition, and eventually, thanks to the work of scholars like Max Nettlau, Déjacque was rediscovered and established as an anarchist pioneer. Libertarian was then incorporated into the anarchist tradition and was used for a long time almost entirely to refer to anarchists. Iain McKay has documented some of that anarchist history in "150 years of Libertarian" and "160 Years of Libertarian."

The right-wing use of the term would largely come in the 20th century, but there is one interesting wrinkle in that origin story, since in 1858 Proudhon himself made use of the term libertaire on at least one (but perhaps only one) occasion, to describe "partisans of free trade, of laissez faire, laissez passer, of every man for himself, etc.."