His most notable science fiction works are a series of novels, the Pelbar Cycle, set in North America about a thousand years after a "time of fire", in which the world was nearly totally depopulated. The novels track a gradual reconnection of the human cultures which developed. Much of the action takes place in the communities of the Pelbar, along the Upper Mississippi River — in the general vicinity of Elsah. Several cultures, including the matriarchal Pelbar, join together in the Heart River Federation. Others, especially the tyrannical Tantal and slave-raiding Tusco, fall apart after suffering defeats. The predominant characters are change agents: Jestak, Stel and his wife Ahroe Westrun. All are Pelbar. Williams won the John W. Campbell Award for Best New Writer in Science Fiction in 1983.
He is also known as a writer of haiku, senryū, and tanka, and wrote a number of essays on the haiku form in English. In a 1975 essay, he coined the term "tontoism" to refer to the practice of writing haiku with missing articles ("the", "a", or "an"), which he claimed made the haiku sound like the stunted English of the Indian sidekick, Tonto, in the Lone Ranger radio and television series. Williams was the president of the Haiku Society of America (1999) and vice president of the Tanka Society of America (2000).
The Day of Strawberries, edited by Paul O. Williams (San Francisco: Two Autumns Press, 2004) — the companion chapbook to the Haiku Poets of Northern California’s fifteenth annual Two Autumns poetry reading series