The illegitimate son of the Norman nobleman Rauf of Bulaire, Earl of Lessford, he has been raised as a Saxon by his mother the Lady Hild and maternal grandfather Alfgar, a belted knight whose lands were confiscated after the Battle of Evesham and given to his bitter enemy, the drunkard lord of Tressling.
The Countess of Bulaire, known as "the Norman woman" and the cause of Walter's illegitimacy when she married Rauf (thereby breaking his chivalric vow to Hild), has taken revenge by hanging six commoners without a trial while imprisoning their families.
Walter is summoned to Bulaire Castle for the funeral but stops first at Gurnie, where he finds his mother enfeebled and the impoverished Alfgar, against all knightly traditions, in trade collecting discarded metals to sell so that he can make cheese.
Walter's inheritance gets them as far as Antioch, where they meet Lu Chung (the "Bird Who Feathers His Own Nest"), the immense and corrupt Chinese agent of the powerful Greek merchant Anthemus, and are permitted to barter for entry into his service.
Impressed by Walter's cleverness and Tristram's physicality, Anthemus makes a place for them on a gift-bearing caravan, including a harem of 81 beautiful women, heading east to the court of Kublai Khan.
Anthemus shows his contempt for them by positioning them at the rear of the train, giving them the small black thief Mahmoud ibn Asseult as their servant boy, and providing a poor yurt and equipment borne by sickly camels.
On the eve of their arrival in Maragha, where they are to join up with their escort, Mongol general Bayan of the Hundred Eyes and his army of the Ilkhan, one of the women – the sister of Anthemus, Maryam (characterized as the Black Rose, a nickname for the spice cloves) – escapes the harem.
Additional tension arises when Maryam gives Tris, who speaks only English, lessons in Bi-chi, the Mongolian-based pidgin of the caravan trade, causing Walter (who earlier tried and failed to do so) to resent being left out.
The journey east sees Walter curry the favor of Bayan through being a competent chess-player and Tristram demonstrate the power of the English longbow instructing an astonished horde.
Caught in the act as he is about to escape, he is honest with Bayan – who considers him a friend – about his motives but is punished by the Rope Walk, an ordeal that gives a small chance to live.
He learns that Bayan did not pursue the others, and when it becomes clear that he will recover sufficiently to return to the general, has renewed hope of finding the others in the Sung capital of Kinsai.
Bayan, to spare the great city and its occupants from total destruction, assigns him the mission of accompanying the Sung peace envoy Chang Wu back to Kinsai in the guise of a Western scholar to convince the Chinese to surrender.
Almost as dire, the Bird Who Feathers His Own nest has also arranged to sell Maryam back to Anthemus through the corrupt and despotic silk merchant, Sung Yung, who is the power behind the war faction.
The three are reunited but confined in the Great Interior Palace, prisoners treated as gods, receiving daily gifts, including much jewelry, many gems, and a priceless porcelain vase.
Using gems sewn into the hem of her garments, Maryam then made her way with agonizing slowness to India, having given birth in Amboyna along the way to a blond, blue-eyed son she named Walter.
But for the first time, communicating in Greek, she is able to relate the story of her escape, reaping the good fortune of being placed on a new Venetian bireme set for its maiden voyage to Marseilles.
A year after leaving India Maryam falls deathly ill in Marseilles but is cared for by an old French innkeeper, Pierre Marchus, who feels a responsibility to look after pilgrims traveling through the port.