At the very least, we have some Atheistic thoughts being expressed back as far as ancient Greece. For instance, Protagoras, who lived through most of the 5th century B.C.E. said that "Concerning the gods I am unable to discover whether they exist or not, or what they are like in form." While this is not outright denial, it is something very against the grain of Greek society. As Cicero mentions when referring to this quote, "I can well believe that this example has discouraged many people from professing such an opinion, since an expression of doubt could not escape punishment." Again, Cicero brings up an example of Atheism in Greece, "Again did not Diagoras, who was called the Atheist,... openly deny the existence of the gods?" He also wrote that "Diagoras,... was accused of impiety. Fearing the people, he fled from Athens. The Athenians announced the reward of a silver talent for the man who killed Diagoras." So according to Cicero, we would believe that open Atheist would likely end up punished by their communities, and skirting the line of Atheism such as Protagoras did, was very dangerous.

Despite the fact that Atheism existed in ancient Greece, from what we know about Greek society in antiquity, it is unlikely that Atheism was prominent. I would also say that this is the earliest example I know of and it is entirely possible that recorded evidence of Atheism exists even further back.

Valerie M. Warrior, Greek Religion: A Sourcebook. 208-209