Book One

In 1273 in England, Walter of Gurnie is a clerk (student) at medieval Oxford. 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. Walter is in love with Tressling's beautiful daughter Engaine but is below her station. After participating in a student riot (led by new acquaintance Tristram Griffen, son of a fletcher and a chamber-deacon student himself) to rescue two fellow students from being hanged by the local watch, Walter attends a lecture by Friar Roger Bacon and is inspired to journey to the far-away semi-mythical land of Cathay. Walter and Tristram elude a hunt for them as leaders of the riot but Walter learns that his father has been killed by an arrow through the heart. 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. Tristram seeks him out to warn him that he is going to lead a raid on the Bulaire castle to free the families. After Walter sees that the children have been starved, he devises a plan for Tristram and his men to steal into the castle to rescue the families. The next day Walter encounters Engaine, who tells him she has reluctantly resolved to marry Edmond, Rauf's legal heir and Walter's half-brother. In despair but to no avail he argues that if not for a shipwreck that led Rauf to marry the countess, Walter would be the legitimate heir and marrying Engaine. Walter impulsively makes a vow of devotion to her, echoing Rauf's vow to the Lady Hild many years before. He attends the reading of the will and is bequeathed a pair of boots he has admired since childhood together with an expensive cup. However his father also wills him into the service of King Edward for life, so he decides to flee England, taking Tristram with him.

Book Two

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. With Lu Chung's help she finds her way to the two Englishmen, who agree to help her escape to a sympathetic relative because they are convinced by her blue eyes that she is half-English. The next day Maryam disappears while Walter and Tris win service with Bayan when Tris recklessly but successfully challenges the Mongol bowmen during an archery contest conducted to keep the restless Mongol warriors busy.

They travel with the army now, provided by Bayan with the finest yurt and the best animals, including splendid horses. Maryam has returned, however, finding herself more afraid of her uncle than she had been of Anthemus. Walter agrees to have her travel with them disguised as a dark-skinned servant boy, all three risking the deadly consequences that would follow their being caught by the Mongol general. 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. Little by little, however, it becomes apparent that Maryam has developed a deep emotion for Walter. 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. Unfortunately, the spiteful Mongolian Ortuh the Stammerer learns of their secret, and Walter decides his party must abandon the caravan with Lu Chung. While the rest flee south into China, Walter steers the caravan off course sufficiently to gain time for the runaways' escape. 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 survives only because the enraged Ortuh violates the rules just as Walter is on the verge of being killed, permitting Bayan to end the punishment.

Left behind in the village where he was caught, with Bayan paying for his care, Walter spends two weeks in a semi-coma and many more recuperating from broken bones. 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. In the third year after leaving England, Walter rejoins Bayan just as he destroys the Sung navy on the Yangtze River, the last task before taking the capital. 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. Once in the Chinese capital, Chang Wu directs a search for Tris and Maryam while Walter meets with "men of substance" in the city to pursue peace. He finds that Kinsai is overwhelmingly in sympathy with the peace proposals but that the war faction has thus far been able to keep it from the Dowager Empress, the Sung regent.

On the day that Walter is to speak with the Dowager Empress, Lu Chung is captured and provides information about the fate of the others. Tris was betrayed by Lu Chung to bandits and probably killed. 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. Walter's conscience, seeing that vows of chivalry are often futile and harmful, compels him to break his vow to Engaine and contrive to wed Maryam in the very clutches of Sung Yung, putting her beyond the power of Chinese magistrates to enforce the criminal transaction. However, as soon as they are married he realizes how completely he loves Maryam. Even better for his mission, the public disgrace of Sung Yung foments a riotous rebellion among the populace who kill the silk merchant and attack the shops of other merchants suspected of wanting war. The ability of common men to exert control on their own destinies, and to work for themselves on their own land, fills Walter with disgust for the feudal system in England.

Walter keeps his audience with the Dowager Empress, but unfortunately his blond hair, and the fact that the blond Tris is not dead but also in Kinsai, fulfills an ancient proverb of "two birds of golden plumage out of the West" whose appearance will end the peril of destruction. The Dowager Empress refuses to surrender. 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. The young couple find happiness together in their luxurious Abode of Everlasting Felicity. Knowing the Bayan is near, Walter has a report smuggled out of Kinsai informing the general of the widespread desire for peace and his own confinement. Chang Wu arranges their escape by sea, but other peace forces try but fail to have the Englishmen drowned by the vicious river tide. As a result, Maryam is unable to reach the ship before it departs.

Book Three

Five years after raiding Bulaire, Tris and Walter return to London, rich with presents from the Dowager Empress. Their legal troubles appear to have become moot; King Edward is, if not a revered monarch, a respected one who considers himself English first, with an obligation to better the lot of the common man. Walter learns that his mother died a year after their departure and that Engaine married Edmond and has a son by him. The new Earl of Lessford is more avaricious and oppressive than even his mother, hanging common men in revenge for the raid and barbarically driving others into banditry until open warfare exists between noble and commoner. Walter turns his share of their wealth into gold to pay his debts and redeem the cup he pawned to finance his adventure. Walter has knowledge of many wondrous inventions from the east – papermaking, gunpowder, the telescope, and the compass – but proof of their existence and Walter's copious notes of all he'd seen have been left behind during their escape. Walter returns to Gurnie to find his grandfather prospering in trade. Their reunion is disrupted when Engaine comes to Gurnie with her son, seeking sanctuary from her husband.

In the meantime, Chang Wu sheltered Maryam following the attempt to drown the Englishmen and after three weeks arranged a ship for her to leave, just a week ahead of Bayan's invaders. 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. Knowing none of the languages of the ports they reached, she used her wealth and the single word "London" to reach Konkan. As Walter arrives at Gurnie, Maryam, her year-old son and Mahmoud are at last able to gain passage on a ship bound for Aden.

Walter offers to provide Engaine support so that she may live in London while petitioning the king for return of her inheritance that Edmond seized when they married. Edmond comes to claim her but Walter with eight archers of Gurnie stands with her and he cowardly backs down. Engaine, knowing Walter is married, calls Maryam a heathen and tries to undermine his marriage vows. Tris becomes the leader of the commoners' resistance. Walter escorts Engaine to Bulaire on the way to London where they discover that Edmond hanging with an arrow in his chest from the same tree that his mother hanged the six commoners five years before. Engaine's infant son is now Earl of Lessford, which restores her estates and makes her more determined than ever to have Walter obtain an annulment from Maryam.

Six months later Maryam has reached Venice, finding the Christian city far more hostile and contemptuous than at any of her Eastern stops. 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. In Gurnie, Walter begins a paper-making enterprise with his grandfather, whose fortunes continue to prosper when King Edward restores his forfeited lands. Tris, on the other hand, has gone into hiding, a fugitive after the death of Earl Edmond. When one of the paper-makers at last discloses Tris's hiding place, Walter visits him in the wild, craggy valley Scaunder Clough. Before Walter can bring him items for comfort, however, news reaches him that Tris died from a fall shortly after their visit. His grandfather grows frail, without hope of ever seeing his restored lands again, but names Walter his heir by endorsing his plan to give small tracts of their lands to the people living and working on the estate.

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. She offers a small pearl, the last of her gems, in hopes it is payment enough to cross France. Months later Walter has a long audience with King Edward, telling him in detail of all he has seen. Though the rest of the court is contemptuous, the king appreciates his story and bestows on him a name, knighting him Sir Walter Fitzrauf. The next morning the queen, Eleanor of Castile, happily tells Walter that a small, sickly woman has been reported in London, wandering the streets and shouting the only other word of English she knows: "Walter." His father's former squire brings Walter together with his wife, three-year-old son, and faithful servant Mahmoud. Maryam will recover, and Walter vows to have his son christened "Walter Alfgar Edward Rauf Fitzrauf."