Another question was posted that asked about one such story and it was rightly pointed out that there are many such stories.
What I am interested in is a specific thing: The first story in which at first the reader is led to believe it is taking place in our own distant past but it turns out it is our future, a future in which we have been reduced to savagery.
My guess is that this is a very old idea because, for example, Plato suggests a civilization that was more advanced than his own (I think). I know that as late as the 1600s, many in Europe believed that the ancients (Rome/Greece) somehow knew more than people of that time.
So the idea of a descent from a previous enlightened time to one less enlightened is very old. I am then guessing that even the 19th century has such stories. The Time Machine certainly shows the Time Traveler people who have descended, not exactly into savagery, but into something less than the people of his own time. But importantly, the TT knows this because he knows how many years into the future he has traveled.
An important aspect of the question is the element of surprise -- if not for the reader for the main character -- he might be a non-savage himself or he could be a "savage" who perhaps discovers that ancients existed who had great cities, etc.