PhatCatholic recently addressed a question related to the question above, by posing the following question (link to source):
When was Purgatory first talked about?
The earliest reference to Purgatory that scholars have found so far comes from The Acts of Paul and Thecla, which was written around 160 AD. In that work, we read the following:
"And after the exhibition, Tryphaena again received her [Thecla]. For her daughter Falconilla had died, and said to her in a dream: 'Mother, you shall have this stranger Thecla in my place, in order that she may pray concerning me, and that I may be transferred to the place of the righteous'"
Notice how Thecla will be praying for Falconilla, even though Falconilla has already died. Prayers for the dead implies the doctrine of Purgatory b/c Purgatory is the only place or state where a soul could reside in which prayers would be necessary or beneficial. Souls in heaven have no need of our prayers and there's no point in praying for the damned, who can never be freed from Hell.
Note also that the doctrine of Purgatory wasn't invented in 160 AD, it's just that the earliest reference to Purgatory that we have comes from that period.
She does pray for a dead girl. The problem is this - there is no indication that the place that the girl is in is anywhere other than hell. PhatCatholic discards the idea that it could be hell that is referenced, because that wouldn't be orthodox.
I agree that it wouldn't be orthodox - but Purgatory isn't orthodox either (and likewise prayers for the dead in general are not orthodox). The fact that it has come to be accepted by the papists doesn't make Purgatory any more orthodox than the idea of successful intercession on behalf of souls in hell.
And the idea of an error with respect to intercession for souls in hell is not so farfetched. After all, it is alleged that Pope Gregory I interceded on behalf of Trajan, who was in hell, and that Trajan was released by Gregory's intercessions.
Furthermore, Suarez, De Pecatis, Disp. vii. 3, claims that the possibility of such deliverance is an open question, and Estius, in Setent. iv (Disp. xlvi. 241), claims that many people have been so delivered. Even Thomas Aquinas himself seems to credit the legend of Trajan's release from hell, excusing this oddity by stating: "Trajan had not been finally doomed to hell, but only provisionally, and that his deliverance was granted to him as an exceptional privilege." (I should note that Aquinas appears to recognize the truth that "there is no redemption in hell" - for he places that phrase in the mouth of an objector on the question of whether the priesthood of Christ endures forever.)
There's an important road-block left out of PhatCatholic's analysis: there is no indication that the girl was previously a Christian or that she was baptized. In short, there is no reason to suppose from the story that she was in any place but Hell. Such, it appears from several reports I have read, was the opinion of John of Damascus, though I have not been able to find a precise citation.
Thus, upon weighing this supposed early testimony for the existence of Purgatory, we find it to be nothing but optimistic anachronism. There is no mention of Purgatory in the text, and no reason (except wishful thinking) to make us believe that Purgatory is referenced. That a fictional tale of Paul's life might include some theological errors is to be expected. After all, the same tale has the heroine, Thecla, baptizing herself in a ditch of water. In the end, it would be a mistake to view this tale from the fictional "Acts of Paul and Thecla" (apparently a work of the late second century) as teaching the modern Roman Catholic doctrine of purgatory. It would be the sort of mistake one might make if one was disparately grasping for straws of the innovated doctrine of Purgatory in the ECF's. Nevertheless, it is a mistake: an anachronistic eisegesis of the document. Purgatory is not to be found in the text, and can only be added in through eisegesis. In short, the claim for the earliest evidence of Purgatory must wait its actual innovation later in history.
P.S. If one is going to imagine Purgatory into the text of the "Acts of Paul and Thecla," why not add in the Limbus Infantum (Limbo)? If we let eisegesis be the methodology, there is no barrier. We can insert whatever theory we want, willy-nilly. By requiring the reader to let the text speak for itself, these problems can be avoided.