Extrapolée à partir de l’Évangile selon Matthieu (II, 2-11), la légende des Rois Mages connaît un succès grandissant. Les Rois vont peu à peu se voir dotés d’une identité et d’une histoire. Jacques de Voragine dans la Légende dorée en a rassemblé et fixé une partie et son livre connut un immense succès au XIV^e siècle. Marco Polo n’a pas pu le lire avant son départ, mais il en a certainement eu connaissance à son retour. Les éléments légendaires qu’il apporte semblent plutôt provenir des chrétiens d’Orient.

Il parle de la grande cité de Perse
La Perse est une grande province. Dans l'Antiquité, elle était brillante et splendide. Mais les Tartars l'ont pillée et détruite. C'est de Sabah en Perse que partirent les trois rois mages qui vinrent adorer le Christ. Ils sont enterrés dans la cité de Saba, côte à côte, en trois grands et beaux sépulcres surmontés d'une maison carrée. Leurs corps sont toujours intacts, avec cheveux et barbe. Ils s'appelaient Gaspar, Melchior et Balthazar.
Marco Polo questionna les hommes de la cité de Saba pour connaître la vie de ces trois mages. Personne ne sut rien lui en dire. Il se rendit, à trois journées de là, au château de Cala Ataperistan, qui signifie en français le "château des adorateurs de feu". Et c'est bien vrai, car les habitants de ce château adorent le feu, et voici pourquoi.
On raconte qu'autrefois trois rois de ce pays s'en allèrent adorer un prophète qui venait de naître. Ils apportaient en offrande de l'or, de l'encens et de la myrrhe. S'il acceptait l'or, il serait roi de la terre, s'il acceptait l'encens, ce serait un dieu, et si enfin il acceptait de la myrrhe, il serait médecin. Or voici qu'arrivé là où l'enfant était né, le plus jeune de ces rois entra dans la pièce et trouva l'enfant d'un âge identique au sien. Il sortit émerveillé. Puis le roi d'âge moyen entra, et il trouva également l'enfant d'un âge identique au sien. Il en sortit tout émerveillé. Enfin, le plus âgé des trois entra, et il lui arriva la même aventure qu'aux deux autres. Il sortit tout pensif. Les trois rois se racontèrent alors ce qu'ils avaient vu, et ils en furent émerveillés. Ils décidèrent d'entrer ensemble dans la pièce. Ils virent cette fois-ci un enfant de treize jours, l'âge qu'il avait réellement. Ils l'adorèrent, et l'enfant accepta les trois présents, l'or, l'encens et la myrrhe, et leur fit cadeau d'une boîte fermée. Les trois rois s'en retournèrent dans leur pays.