In The Passion, the young Frenchman Henri, sent to fight in the Napoleonic wars, meets a Venetian woman with webbed feet, Villanelle, in Russia. Together, they flee from the grande armee. Henri falls in love with her, though Villanelle's heart is with another. Henri kills Villanelle's husband and winds up in prison, where Villanelle visits him, eventually bearing his child though refusing to marry him.

As the novel begins, Henri, a new recruit of Napoleon's grande armee, has dreams of serving as a drummer. He is instead assigned the ignoble task of sating the emperor's considerable appetite for spit-roasted chicken. Though disappointed, Henri finds solace in being near the charismatic leader, this despite Napoleon's petulant, grasping behavior. Desperate for fulfillment, Henri wants to believe that Napoleon Bonaparte is worthy of his reputation.

Disillusioned, Henri finds friendship with Domino, a horse keeper who believes in living only for today, and Patrick, a defrocked priest with a penchant for tall tales. Together, they endure the hardships of Napoleon's Boulogne base camp, where France prepares to invade England. Plagued with guilt at seeing so many of his countrymen killed, Henri begins the New Year of 1805 doubting Napoleon's worth.

Meanwhile, a beautiful and mysterious Venetian, Villanelle, meets her heart's desire across a casino card table. This woman, whom Villanelle refers to as the "Queen of Spades," becomes Villanelle's lover. The two women meet whenever the Queen's husband is away. By chance, Villanelle sees the "Queen" and her husband together and is crushed by the obvious love they share. Seeing no future with the Queen, Villanelle begins the New Year of 1805 with a broken heart.

Several years pass. Napoleon and the grande armee arrive at Moscow, but the Russians have already put it to the torch. Disgusted and tired of Napoleon's endless war, Henri deserts with Patrick and a lovely prostitute, Villanelle. Villanelle tells them of how her fat, wealthy husband sold her to the grande armee. She also tells the story of how she literally lost her heart to the Queen of Spades. Posing as husband and wife, Henri and Villanelle soon become intimate.

Henri and Villanelle make their way to Venice, but Patrick falls ill and doesn't survive the trip. Despite the encouragement of Villanelle's parents, Villanelle refuses to marry Henri, referring to him as "brother." Despite this rejection, Henri recovers Villanelle's stolen heart from the Queen of Spades. The two soon run afoul of Villanelle's husband, an old enemy from Henri's past. Henri kills the husband, cutting out his heart.

Henri confesses to the crime and is imprisoned overlooking the Venetian lagoon. Villanelle makes conjugal visits while trying to arrange Henri's release. Henri, however, breaks off all contact when Villanelle, who now carries Henri's child, still refuses to marry him. As Villanelle accepts that the Queen of Spades will never be hers, Henri descends into hallucinatory madness, imagining that he is visited by the souls of long departed friends. Villanelle occasionally trades a friendly wave with Henri from far below the prison window, their daughter by her side. Henri, with surprising lucidity, writes of his continued love her for Villanelle, bearing hew no ill will.