Astolat first appears in the early 13th-century French prose romance Mort Artu, the Death of Arthur, where it is called Escalot and its lady is the Demoiselle d'Escalot, a young woman who dies of love for Lancelot and drifts down a river to Camelot in a boat. In the 14th-century English poem Stanzaic Morte Arthur, the place becomes Ascolot and the maiden is the Maid of Ascolot. But the fullest version of the tale comes from Sir Thomas Malory's Le Morte d'Arthur, composed in the 15th century, where Astolat is the castle of Sir Bernard, a knight of moderate standing who has two sons, Tirre and Lavaine, and one daughter, Elaine, called the Fair Maid of Astolat. Malory places the castle near Camelot, and in his geography Astolat lies on the road between the royal city and Winchester, where King Arthur holds a great tournament.

The story begins when Lancelot, seeking to compete in the tournament in disguise, asks Sir Bernard for shelter. The old knight gladly receives him, and his daughter Elaine falls in love with the stranger at first sight. She begs Lancelot to wear her token, a sleeve of scarlet cloth, upon his helmet so that she may claim him as her champion. Lancelot, who has never worn any woman's token before because his heart belongs utterly to Queen Guinevere, agrees only because he is in disguise and the queen will not recognise him. He rides to the tournament wearing the red sleeve, fights with devastating skill, and wins the day. But in the melee he is gravely wounded by a spear thrust, and his horse carries him from the field. Lavaine, his squire and the younger son of Sir Bernard, finds him bleeding in a hermit's cell and brings him back to Astolat, where Elaine nurses him through fever and delirium for many days.

When Lancelot recovers enough to leave, Elaine confesses her love. She begs him to marry her, or at least to be her lover, offering him everything she has and everything she is. Lancelot, bound by his secret and forbidden love for Guinevere, refuses with gentleness but with absolute finality. He tells her that his heart is given elsewhere, that he cannot love her as she deserves, and that she must find a worthier knight. He offers her a thousand pounds of gold and the promise that he will always be her champion if she marries another. Elaine is devastated. She faints in his arms, and when she wakes she refuses all food and drink. For ten days she lies in her chamber, growing thinner and paler, her life draining away with her hope. On the tenth day she calls her father and dictates a letter to be placed in her hand when she dies. The letter tells her story without blame, confessing her love and Lancelot's innocence, and asking only that he pray for her soul.

Elaine died, and her body was laid in a white barge upon the river, dressed in a gown of white samite, a lily in her right hand and the letter in her left. The barge drifted down the Thames to Westminster, where King Arthur and Queen Guinevere stood upon the bank with the court. Gawain, who had once courted Elaine himself, recognised the boat and the maiden. Lancelot read the letter and was overcome with grief and guilt, for he had never meant to cause such suffering. Arthur ordered a royal funeral, and Elaine was buried with all the honour due to a queen. Guinevere, reading the letter, understood that Lancelot had been faithful to her even in his rejection of the maiden, and her anger at him melted away. But the tragedy of Astolat remained, a place where love had been offered without reservation and refused without cruelty, yet the result was death all the same.

In the 19th century, Alfred, Lord Tennyson took the story of Elaine of Astolat and transformed it into "The Lady of Shalott," one of the most famous poems in the English language. Tennyson kept the river, the barge, the lily, and the letter, but he moved the maiden to a tower on an island, gave her a curse that forbade her to look directly at the world, and made her death the result of seeing Lancelot in her mirror and leaving her loom to follow him. The tower of Shalott became a symbol of artistic isolation, the mirror a symbol of indirect experience, and the poem a Victorian meditation on the cost of engaging with reality. Tennyson returned to the original story more directly in his later Idylls of the King, in the poem "Lancelot and Elaine," where the tower is gone and the maiden is once more the daughter of a lord near Camelot, dying of love in a barge upon the river. Malory had identified Astolat with Guildford in Surrey, a real town beside the River Wey, and though modern scholars debate whether the identification was deliberate or merely convenient, the connection has endured. Guildford still claims the legend, and the name Astolat lives on in the Arthurian imagination as the place where a young woman's love was so pure that it became her doom.