The book's composition weaves around the story of a Kesh woman called Stone Telling, who lived for a while with the people of her father - the Dayao or the Condor people, whose society is rigid, hierarchical and expansionist. The story fills less than a third of the book's total volume, though; the rest is a mixture of Kesh cultural lore (including poetry, literature, mythos, rituals), essays on Kesh culture, and the author's own musings under the pseudonym "Pandora". The book is accompanied by a tape of Kesh music and poetry (often not found with the used copies of the book, but available on order from the publisher).
Unlike most books based on a future earth, Always Coming Home follows Native American and Taoist themes.
Songs in the book were composed by Todd Barton and pictures in the novel were drawn by Margaret Chodos-Irvine.