The novel begins with Loon, a boy from a tribe of Ice Age humans who call themselves the Wolf Pack, being stripped naked and sent into a lonely valley where he is expected to try to survive alone for two weeks as a test of manhood. Despite a rainstorm on the first day, Loon succeeds in using the skills he has been taught by Thorn, the Wolf Pack's shaman. He manages to start a fire, kill animals for food, and make himself clothing. During his trial he encounters a group of Neanderthals (a species of human whom his band calls 'the Old Ones') who attack him, and he injures a leg while escaping them, an injury that will trouble him for the rest of his story. Despite many adventures, Loon completes his trial and returns to the Wolf Pack. At this point it is revealed that he is just twelve years old.

The next section of the novel describes Loon's life among the Wolf Pack, a small band of hunter-gatherers who migrate according to the seasons, hunting caribou in the winter, fish and deer in the summer. Loon's parents are both dead, and he is being raised by Thorn to be a shaman, teaching him about the spirit world and the stories of his people in addition to more practical survival skills. Thorn is a wise but crotchety master who flicks Loon's ears when he makes mistakes. He also teaches Loon to paint cave art in a sacred cave. Another prominent member of the Wolf Pack is Heather, a wise woman skilled in medicine.

Every summer, the Wolf Pack attends a festival called the 'eight eight' where the various local bands meet to dance and share stories, and where the shamans corroborate their astronomical observations. At one such festival, Loon meets Elga, a young woman who wants to leave her own tribe and join another. She and Loon fall in love and, much to Thorn's displeasure, they marry and have a child. Loon continues to learn the way of the shaman, rejecting Thorn's belief that shamans must not marry.

At the next year's festival, however, Elga is abducted by men from a northern tribe. Loon, helped by a traveler called Pippiloette, follows them, but after a few days Loon too is captured by the men while Pippiloette escapes. The men, who belong to a band called the Jende, take them far to the north, to the foot of the great ice cap on the shores of the Great Salt Sea. Despite living in the frozen north, the Jende live well, thanks to their use of captive slaves to do much of their work. Loon and Elga are kept separate, and Loon is forced to work with the Jende as they hunt through the winter.

Meanwhile, Pippiloette returns to the Wolf Pack to explain what has happened. Thorn decides to follow the Jende's trail and rescue Loon and Elga. He enlists the help of Click, a strong and friendly Old One (Neanderthal) who has befriended the Wolf Pack after Heather gave him medical aid. Click cannot speak like a human, communicating only in broken phrases, whistles and clicks, and his mind is intelligent but not human, yet he and Thorn learn to understand each other. Thorn and Click travel hundreds of miles to the north and rescue Loon and Elga in a surprise attack on the Jende. The four then travel all the way back to their own land, facing many dangers, and with Loon's bad leg causing extreme difficulties. The last part of the journey is across snow and is extremely difficult. Near to home, Click dies, and Thorn reluctantly decides that they must eat his body to survive. Finally, they return home, to the delight of their Pack.

Life returns to normal for Loon and Elga, but Thorn is troubled by the ghost of Click, who haunts him, apparently in anger at the way his body was treated. The three bury Click's bones, and Loon feels that Click's spirit is absorbed into his bad leg, but Thorn continues to see the ghost and remains troubled. The Wolf Pack decides not to attend the next eight-eight festival to avoid the Jende, but they plan to attend the following year. Knowing that the Jende will demand recompense for the attack on them, Thorn proposes that Loon offer them a set of the snowshoes that he has been testing and improving, which are made from strong barks unavailable to the northmen. Loon spends months experimenting with and refining his snowshoe design, and at the festival, when the Jende demand the return of Elga, she defiantly refuses, and the northmen accept the offered snowshoes with grudging admiration.

As the months pass, Thorn begins to sicken. Still haunted by the ghost of Click, he dies advising Loon to pass on the knowledge he has learned to future generations. Later, Loon visits the cave alone, and paints animals that he has observed: fighting rhinos and four horses. His lamp goes out and he becomes lost in the dark for four days, but is rescued by Elga and others who take him back out in what he describes as a spiritual rebirth. Back in the camp, he dreams of Thorn's ghost, who vows to haunt him. The novel ends with Loon training his son to be a shaman, and flicking his ears when he misremembers things.

The text of the novel does not explicitly identify its geographical or temporal setting because it is told from the point of view of characters who lack our modern understanding of the world. However, Robinson has stated that the setting is 32,000 years ago in what is now southern France, and that the cave where Thorn and Loon paint is the Chauvet Cave, a recently rediscovered site of impressive cave art.^[1] In the novel's final chapter, Loon paints the fighting rhinoceroses and the four horse heads that can be seen on the walls of the real-life cave.

Shaman received mixed reviews in Publishers Weekly ("entertaining but slight")^[2] and Kirkus Reviews ("Richly detailed but with a disappointingly modest plot from an author renowned for ambitious works.")^[3] National Public Radio's review was more positive, praising the vividness of the novel's setting.^[4] Writing in The New Yorker, Tim Kreider described Shaman as one of Robinson's lesser novels, criticizing its depiction of Ice Age society: "There’s evidence to suggest that prehistoric cultures would’ve seemed far more savage and alien to us than Robinson imagines here."^[5]