The story of the Fair Maid of Astolat begins when Arthur departs with his knights for a joust that was to be held fifteen days after Our Lady's Day of the Assumption.Originally, Lancelot was not going, but at Guinevere's urging, he departed to join King Arthur at the court of Astolat. When he arrived there, he did not meet with Arthur. Instead he went to the castle of Astolat. Lancelot was well received by Sir Bernard of Astolat who informed him that his two sons were going to take part in the joust as well. Sir Astolat also had a daughter, Elaine or The Fair Maid of Astolat. She fell hopelessly in love with Lancelot. She asked Lancelot if he could wear a token of hers at the joust. However, being faithful to Queen Guinevere, Lancelot responded that if he was to wear a token, he must joust in disguise. At the joust, Sir Lancelot was victorious and he slew many knights. But Lancelot left the joust before he could have been declared victor since he was wounded. During this time, Sir Gawain arrived at the castle of Sir Astolat and was asked by Elaine who the victor was at the joust. Sir Gawain responded that the knight who won was unknown, but that this unknown knight bore a white shield. The lady then responded that the knight who won was her true love.

When Gawain saw the shield of Lancelot in the keeping of the fair maiden, he informed her that Lancelot was the King's Champion. Gawain returns to court and announces that the knight who won the joust is Lancelot, upsetting the Queen. She is filled with jealousy and exclaims: "No matter, though he be destroyed, for he is a false traitor knight."

By this time, the Maid of Astolat has found her love Lancelot at the place where he is receiving medical care. She cares for him day and night. Once Lancelot is healed, he leaves with the fair maiden to return to Astolat, and there she asks him to marry her. However, Lancelot refuses because he has vowed never to be a wedded man. Moreover, he is devoted to Guinevere. The Lady is so sadded by Lancelot that she weeps and cries, refuses to eat and, eventually, dies of heartache. However, before she dies, she asks her father to place her body in a barge left to float down the Thames until it comes to Camelot. Her father carries out her wishes, covering the barge with black samite. When the barge arrives in Camelot, Arthur sends knights to investigate. There, the letter is recovered from the hand of the fair maid. Lancelot is shocked upon reading the letter and buries her with all honor and worship of King Arthur.

The story of the Fair Maid was retold by Alfred Lord Tennyson in the nineteenth century in his poem "The Lady of Shalott."This was his first published Arthurian poem and the subject of this famous painting by JW Waterhouse (1883). When he composed "The Lady of Shalott," Tennyson was unaware of the story told by Malory: "I doubt whether I should ever have put it in that shape if I had been then aware of the Maid of Astolat in Mort Arthur."