A holy monk named Zosimus (later Saint Zosimus) was wandering and praying in the desert near the river Jordan during Lent in the year 420 A.D., when he saw a movement from the corner of his eye. Startled out of his prayer, he turned to see a very sunburned, very naked, person running away from him and deeper into the desert. Saint Zosimus was understandably astonished by this, and chased the person down, calling out in the name of God for them to stop and wait for him. The runner obligingly stopped, but refused to turn around. To continue Zosimus' series of shocks, the runner then called out to him by name, saying that she was a woman, and naked, but if he would throw her his cloak, she would cover herself so she could turn and ask for his blessing.
When Saint Zosimus had given the woman his cloak, she turned around and once again called him by the name Abba Zosimus (Father Zosimus), and asked for his blessing. Zosimus, realizing that he was in the presence of a very holy woman indeed, prostrated himself, and began to beg her for a blessing. They both lay there on the ground for a bit, each saying "Bless me!", until the woman finally gave in to Saint Zosimus' pleadings and said "Blessed is God Who cares for the salvation of men and their souls."
When Saint Zosimus asked her to pray for him and the world, the woman consented, and lifted her hands toward heaven to pray. While she was speaking softly and praying, Saint Zosimus lifted his eyes from the earth to find that she was levitating an arm's length above the ground. After more prostration and pleading on the part of Saint Zosimus, the mysterious hermit agreed to tell him her story, but only so that he might see what a wretched sinner she was, and that he might see the great mercy and forgiveness God had for sinners.
The woman's story began with her birth into a well-to-do Egyptian family (around 344 A.D.). After running away to Alexandria when she was only 12, she lived the life of a dancer and prostitute for 17 years, often refusing payment for her services, and always seeking more men to seduce. One day, she heard of a ship leaving for Jerusalem, filled with pilgrims who wanted a chance at seeing the true cross of Jesus Christ. Thinking that the flood of pilgrims would provide her with a stockpile of new lovers, the woman obtained passage on the ship, prostituting herself for her fare.
Upon her arrival in Jerusalem, the woman went with the pilgrims to the church of the cross, out of curiosity. When she tried to enter the church, however, an invisible force prevented her, although other people could move freely through the door. Realizing that her sinfulness was the reason she was not permitted to enter, the woman fell to the ground in tears of repentance. She looked up and saw an icon of the Blessed Virgin Mary, and prayed to the Holy Mother that she would be able to enter and worship the cross that Jesus had died upon for her sins. With that, she found she was able to enter the church and do homage.
Guided by the Blessed Virgin, the woman set out for the desert across the river Jordan, to leave society and its temptations, and live as a hermit. Taking only three loaves of bread with her, she crossed the river and journeyed deep into the desert, where she lived for the next 47 years struggling with her lust, and praying for forgiveness for her sins. She lived off the three loaves of bread for the entire time, and Saint Zosimus was the first person she had seen in all those years.
Saint Zosimus was amazed, and once again asked the holy woman to pray for him and for the world. She agreed, asking only that he would return to her on Holy Thursday in one year, so that she might receive Holy Eucharist one more time. Readily agreeing to this, Saint Zosimus returned to his monastery. Only after he had left her did he realize that he didn't even know this holy woman's name.
True to his word, Saint Zosimus returned to the Jordan river the next year before Easter, on Holy Thursday, carrying some of the Blessed Sacrament with him. He saw the holy woman approach the far bank, make the sign of the cross over the river, and then walk across on the water. When she reached the near shore, she and Saint Zosimus prayed together, and she partook of the Holy Eucharist. Afterward, she prayed to heaven in the words of Simeon: "Now thou dost dismiss thy servant, O Lord, according to thy word in peace, because my eyes have seen thy salvation."
She then asked Saint Zosimus to meet her one year later in the place where he first saw her, which Zosimus agreed to. When he returned to the desert in one year, however, he found her lying dead on the sand. Next to her uncorrupted body she had written a request for Saint Zosimus to "bury on this spot the body of humble Mary". Thus, for the first time, Zosimus knew her name. And, as if there weren't enough miraculous events associated with Mary's life, Saint Zosimus was aided in the digging of her grave in the hard earth by a lion.
Saint Mary of Egypt is the patroness of penitent women, reformed prostitutes, and sexual temptation. Her feast day is celebrated April 1 in the Roman Church, and April 3 by the Greek Church. In icons, she is often portrayed as a thin, sun browned woman in a cloak (with the disheveled uncovered hair that is the iconic mark of a reformed harlot); either receiving Holy Eucharist from Saint Zosimus, with three loaves, or with a lion.
Sources
http://www.newadvent.org/cathen/09763a.htm
This has the entirety of Saint Sophronius' story of the life of Saint Mary of Egypt, written around 625 A.D., and supposedly gotten directly from the monks at Saint Zosimus' monastery:
http://www.fatheralexander.org/booklets/english/mary_egypt_ext.htm
http://www.catholic-forum.com/saints/saintm22.htm