In the account in The Hobbit (chapter 5, Riddles in the Dark) we're told that '...the riddle-game was sacred and of immense antiquity...' and indeed Gollum remembers asking and guessing riddles with his fellow Hobbits in his early life before he went into exile, which would mean that the game dated back to at least III 2470 or so.

The Prologue to The Lord of the Rings (part 4, Of the Finding of the Ring) goes even further, describing the game as a tradition so formally organised as to have its own 'Authorities'. Since both Bilbo and Gollum were aware of this tradition, the game must date back to the time before their two cultures diverged. This is harder to date, but it was probably the point at which the Stoors of the Angle divided in about III 1356. That would make the Riddle-game fifteen hundred years old or more when Bilbo and Gollum played it beneath the Mountains.