The novel follows two parallel narratives. One thread, written by a character named Jonathan Safran Foer, is a fictional history of Trachimbrod, a Ukrainian shtetl destroyed by the Nazis in 1942. The other story, narrated by a character named Alex, recounts his, Jonathan's, and his grandfather's present-day quest to find Trachimbrod and a woman named Augustine who saved Jonathan's grandfather during the war.

In Alex's story, Jonathan explains the purpose of his trip: he is trying to find a woman named Augustine, who helped his grandfather, Safran, escape the Nazis. Jonathan hires Alex and his grandfather, who works for Alex's father's Odessa-based Heritage Tours company, to guide him in Ukraine. The three men, along with Grandfather's deranged dog, travel from Odessa into the Ukrainian countryside searching for Trachimbrod.

The novel's other narrative thread describes the history of Trachimbrod, beginning with a mysterious wagon accident in 1791 that kills a man named Trachim B. and leaves his newborn baby girl, Brod, as the sole survivor. Brod grows up to be Jonathan's great-great-great-grandmother. The book traces the lives of several of Jonathan's ancestors, particularly Brod and her descendant Safran, who was Jonathan's grandfather.

In the end, the search party finds an old woman named Lista who is the last survivor of Trachimbrod. She tells them how the Nazis massacred the town's Jews. Jonathan collects artifacts from the site to remember his family's past. The novel explores themes of memory, history, and the search for identity and meaning in the aftermath of the Holocaust.