The earliest record (I have) found (searching the Internet) is the Persian Book Shahnameh, of which I know nothing more than the Wikipedia entry:
The Shahnameh or Shah-nama (Persian: شاهنامه Šāhnāmeh, "The Book of Kings") is a long epic poem written by the Persian poet Ferdowsi between c. 977 and 1010 AD and is the national epic of Iran and related societies. Consisting of some 60,000 verses, the Shahnameh tells mainly the mythical and to some extent the historical past of (Greater) Iran from the creation of the world until the Islamic conquest of Persia in the 7th century.
Incidentally, it might be interesting to know for western ignorant folk (like me) that this book was "pivotal in reviving Persian language after the Arabic infulence". Back on topic, because I do not have a copy of it at hand, I relied on a random website for the translation of the relevant passage, as reported in Yalom's book [7] (pages 4-5):
The Persian epic Book of Kings (Shah-nameh), written by the great poet Firdausi (c. 935–1020), gives an amusing account of how chess made its way from India to Persia. As the story goes, in the sixth century the raja of India sent the shah a chess set made of ivory and teak, telling him only that the game was "an emblem of the art of war," and challenging the shah's wise men to figure out the moves of the individual pieces. Of course, to the credit of the Persians (this being a Persian story), one of them was able to complete this seemingly impossible assignment. The shah then bettered the raja by rapidly inventing the game of "nard" (a predecessor of backgammon), which he sent back to India with the same challenge. Despite its simplicity relative to chess, the intricacies of nard stumped the raja's men. This intellectual gambling proved to be extremely costly for the raja, who was obliged to pay a heavy toll: two thousand camels carrying "Gold, camphor, ambergris, and aloe-wood,/As well as raiment, silver, pearls, and gems,/With one year's tribute, and dispatched it all/From his court to the portal of the Shah."
Another story in the Shah-nameh tells how chess was originally invented. In this tale, an Indian queen was distraught over the enmity between her two sons, Talhand and Gav, half brothers with respective claims to the throne. When she heard that Talhand had died in warfare, she had every reason to think Gav had killed him. The sages of the kingdom, the tale has it, developed the chessboard to recreate the battle, and show the queen clearly that Talhand had died of battle fatigue, rather than at his brother's hands. The Persian term shah mat, used in this episode, eventually came down to us as "check mate," which literally means "the king was dumbfounded," though it is often translated as "the king died."
The Shah-nameh version of the birth of chess vied with another popular legend in which a man named Sissa ibn Dahir invented the game for an Indian king, who admired it so much that he had chessboards placed in all the Hindu temples. Wishing to reward Sissa, the king told him to ask for anything he desired. Sissa replied, "Then I wish that one grain of wheat shall be put on the first square of the chessboard, two on the second, and that the number of grains shall be doubled until the last square is reached: whatever the quantity this might be, I desire to receive it." When the king realized that all the wheat in the world would not suffice, he commended Sissa for formulating such a wish and pronounced it even more clever than his invention of chess.
Another source [8], also discusses this legend, and the earliest recorded occurence is again in Firdausi. However the author speculates about the earlier development of the theme. According to al-Masudi's early history of India, shatranj, or chess
was inventend under an Indian king, who expressed his preference for this game over backgammon. [...] The Indians, he adds, also calculated an arithmetical progression with the squares of the chessboard.
[...] The early fondness of the Indians for enormous calculations [9] is well known to students of their mathematics, and is exemplified in the writings of the great astronomer Āryabaṭha (born 476 A.D.). [10]. [...] An additional argument for the Indian origin of this calculation is supplied by the Arabic name for the square of the chessboard, (بيت, "beit"), 'house'. [...] For this has doubtless a historical connection with its Indian designation koṣṭhāgarā, 'store-house', 'granary' [...].
(emphasis added). Now this is really all I could find.
Hope this can mitigate your thirst, cheerio!
[7]: Birth of the Chess Queen, M. Yalom, HarperCollins Publishers
[8]: Art. XIII.—The Origin and Early History of Chess, A. A. Macdonell, Journal of the Royal Asiatic Society, Volume 30, Issue 01, January 1898, pp. 117-141, DOI: 10.1017/S0035869X00146246, Link: http://journals.cambridge.org/abstract_S0035869X00146246
[9]: Indiens Litteratur und Kultur, L. v. Schroeder, pp. 723-4
[10]: Cf. the arithmetical progression attributed to Āryabhaṭa by Sadgurusisya, ed. Macdonell, p. 180
