Travels of William of Rubruck
Itinerarium fratris Willielmi de Rubruquis de ordine fratrum Minorum, Galli, Anno gratia 1253 ad partes Orientales (c. 1253-1255)
William of Rubruck's Itinerarium records the Franciscan missionary's quest, ordered by King Louis IX, to convert the Tatars to Christianity and to gauge their potential as crusading allies.
Like John of Plano Carpini's Ystoria Mongalorum, William's Itinerarium records basic observations about the geography, culture, religion, and daily life of the Mongols. William's account has been more historically useful due to his incisive observations and his clear writing style. As Brewer (p. 162) notes, William was the first European to cast doubt on the veracity of the Prester John legends, though he does buy into Prester John's historical reality.
In Chapter 17 William writes of a powerful Naiman (Nestorian) shepherd who rose to power as King John at the beginning of the twelfth century during the power vacuum created by the death of the "Gürkhan." William is careful to note that the rumors that began to spread about this King John are exaggerations.
From Dawson’s English translation (122-23):
[...]In a certain plain among these pasture lands [of the Carcathayans] was a Nestorian, a mighty shepherd and lord of all the people called Naimans, who were Nestorian Christians. On the death of Coir Chan, this Nestorian set himself as king and the Nestorians called him King John, and they used to tell of him ten times more than the truth. For the Nestorians coming from these parts do this kind of thing-- out of nothing they make a great rumour… I passed through his pasture lands and nobody knew anything about him with the exception of a few Nestorians.
This John had a brother by the name of Unc, like him a mighty shepard, and he was beyond the pastures of these Carcathayans, separated from his brother by a distance of three weeks’ journey, and he was lord of a little town called Caracorum,... King John died without an heir and his brother Unc grew rich and had himself called Chan and used to send his herds and flocks as far as the Mongol boundaries… And the Tartars and Mongols made him their leader and captain.”
See also this useful online article on William and his travels.
More on William of Rubruck.