The first generally circulating paper money is thought to have appeared in China in the tenth century. In his travels through China in the thirteenth century, Marco Polo reported that the Chinese used paper money. Paper money that closely imitated Chinese models is known to have been briefly used in Ikhanid Iran in 1294.
But there’s more to the early history of paper money. Paper money apparently was used in western Asia or Mesopotamia in the tenth century or earlier. The Lives of the Prophets, compiled by the eleventh-century Baghdad-based Islamic scholar al-Thalabi, includes texts on the Companions of the Cave / Seven Sleepers of Ephesus. One of these accounts states:
Then he [Tamlikha] took papers from the money that they had, which were stamped with the seal of Duqyanus [the Roman Emperor Decius], and they were like the light quarter (dirham). … He approached those who sold food and took out the paper he had with him and said to a man among them, “O servant of Allah, sell me some food for this.” The man took it and looked at the imprint on the paper and its inscription and wondered at it, then he threw it to one of his companions, and he looked at it. Then they passed it among themselves, from man to man, wondering at it, and took counsel and said to one another, “This man has come across a treasure in the ground from long ago.”
The text in English translation subsequently shows some confusion between paper money and coins:
He was brought before the two pious men, Armus and Astiyus, and when Tamlikha learned that he was not going to Duqyanus, he recovered and his feelings became calm. Armus and Astiyus took the papers and looked at them, and were perplexed by them. Then one of them said, “Where is the treasure that you found, young man?” He replied, “I did not find treasure. These coins are my parents’ coins, with the engraving of this city and its minting.” … [one of the two pious men said] “Do you think that we will send you away and believe you that this money is your father’s? For the minting of these coins and their engraving is more than three hundred years old….The treasuries of this land are in our hands but we do not have a dirham or a dinar of this minting.”
In English, coins are minted, while engravings suggest images block-printed on paper. The first quoted section suggests that the paper money was unusual, but the novelty has a historical twist. Taken literally, it implies paper money was used about 250 GC. The confusion between paper money and coins in the second quoted passage suggests that terminology for it had not yet solidified. That in turn implies that experience of paper money was relatively recent. Al-Thalabi’s text is compiled from earlier historical sources. The dating of the source for these passages isn’t clear. These passages provide evidence that paper money was used outside of China at least some time before al-Tha’labi’s death in 1036 GC.
The use of paper money may provide insight into political structure. The intellectually inimitable and indomitable winterspeak insists, “The strength of fiat money depends on the strength of the Government’s ability to demand and collect taxes.” The failed introduction of paper money in Persia in 1294 occurred in a period of poor government administration and intense political rivalries. Earlier use of paper money in western Asia or Mesopotamia may indicate that some political entity there had a powerful, stable administrative structure.
* * * * *
 Additional discussion of China’s first experiences with paper money, and image from British Museum. Here’s Marco Polo’s book in English translation. On paper money in Persia in 1294, see note  and associated text above,
 A sixteenth-century Persian painting of a scene from the Companions of the Cave story appears in the Sackler Gallery’s exhibition Falnama: Book of Omens. Here’s some additional discussion of the evolution of texts and images representing the story.
 Quotations from Brinner, William, trans. 2002. ʻArāʻis al-majālis fī qiṣaṣ al-anbiyā, or, Lives of the prophets as recounted by Abū Isḥāq Aḥmad ibn Muḥammad ibn Ibrāhīm al-Thaʻlabī. Leiden: Brill, pp. 708, 709, 711. Fischel, Walter J. 1939. “On the Iranian Paper Currency of the Mongol Period,” Journal of the Royal Asiatic Society of Great Britain and Ireland, No. 4, pp. 601-4, provides a text (p. 604) that indicates that paper currency existed for a quarter of a dirham, which normally was a silver coin. A dinar was a gold coin.
 Brinner is a leading historian of lives of the prophets. His translation represents a recent, scholarly effort.
 The quoted passages are well-integrated into the text and not likely to be later interpolations. Much commerce flowed across the empires of central Asia in the tenth century and earlier. See Beckwith, Christopher I. 2009. Empires of the Silk Road: a history of Central Eurasia from the Bronze Age to the present. Princeton: Princeton University Press. The use of paper money in tenth-century China almost surely would have been known in tenth-century Baghdad.
 It was the reign of Geikhatu (also spelled Gaykhatu or Gaikhatu). For a brief history of Geikhatu’s reign, see Browne, Edward Granville. 1920. A history of Persian literature under Tartar dominion (A.D. 1265-1502). Cambridge [England]: University Press, pp. 37-9.