Sometimes spelled "Prestor John"
The myth of Prester John is believed to have started around the 1160's when a mysterious letter began to circulate around Europe. Several copies of the letter were eventually made, but the most common version was addressed to Emanuel I, Byzantine Emperor of Rome. Other versions were addressed to the Pope, or the King of France. Prester is a corruption of the word "Presbyter."
Prester John's kingdom was rumored to be made up of the Three Indias. The Kingdom of Prester John was a veritable heaven on earth: free of crime and sin. It was said that it contained rivers of gold, and his letters contain the first written mention of a Fountain of Youth. Prester John himself was said to be decended from one of the Three Magi, and carried a staff of pure emerald. Prester John wrote that he was being attacked by infidels and barbarians and he needed the help of Christian European armies. In 1177, Pope Alexander III sent his friend Master Philip to find Prester John; he never did. He did, however, find Genghis Khan. Philip and his priests were confused, to be sure, but the Great Khan supported complete freedom of religion within his kingdom, and even attempted to practice at least the most basic parts of every religion practiced by those within his domain. At first the priests attempted to convert the Mongols, but soon they found themselves kept with all the rest of the Great Khan's religious advisors. After getting trounced in religious debate by the Buddhists, they returned home.
Legends of Prester John were so widespread that wandering beggars could sometimes earn a few extra coins by claiming that they were emissaries of Prester John on their way to Rome, or some king.
By the 1340's, the letters claimed Prester John's kingdom was Ethiopia. This was important because Christians of this age believed that Prester John's kingdom was the only Christian nation outside of Europe, and it made Ethiopia rather sought after as an ally by European nations, because it was perfectly located for staving off Moslem hordes. By this period, Prester John had stopped asking for help, and turned to a call to arms to take Jerusalem back from the Moslems.
In particular, Portugal, traders that they were, showed interest in attempting to make contact with the priest-king. They sought not only to attain trading rights with Prestor John's Ethiopia, but also to make valuable trading routes to India through his kingdom. For this reason, in 1487 John of Portugal sent Diaz down the coast of Africa to try to reach the kingdom of Prester John. Diaz found the Cape of Good Hope but did not reach Ethiopia. At the same time the king of Portugal also sent de Covilham overland to reach Ethiopia. De Covilham arrived in Ethiopia and was received with great honor by King Eskander.
Whether Prester John's kingdom was in Africa or Asia remained suspect for several more years. A map in 1507 places his kingdom in the vacinity of Tibet, while the Carta Marina in 1516 places it back in Ethiopia. By the 1600's it was thought that Prester John's country was actually Abyssinia.
Sources
http://www.ethiopiaonweb.com/ethiopia/History/middle_ages.htm
http://geography.miningco.com/library/weekly/aa081098.htm
http://www.newadvent.org/cathen/12400b.htm