Volokhonsky was born in Leningrad and graduated from university with a degree in chemistry. In 1973, he emigrated to Israel and then moved to Germany in 1985. Between 1985 and 1995, Volokhonsky lived in Munich, where he worked for Radio Free Europe/Radio Liberty, and in 1995 he moved to Tübingen. His sister, Larissa Volokhonsky, eventually became a translator.
Volokhonsky began writing poetry in the 1950s. He published several books of poetry, some of them together with Alexei Khvostenko. Most of the poetry is ironic and is considered to be descended from Oberiu. Perhaps his most famous piece was lyrics on "Canzona by Francesco da Milano", written by Vladimir Vavilov, the song called "The City of Gold" (Russian: Город Золотой). The song, in turn, would become a hit in the 1980s when it was performed by Aquarium for the soundtrack for the film Assa. Volokhonsky also worked with Leonid Fyodorov, the frontman of the Auktyon, and wrote texts for his albums.