Early Neolithic graves at Jiahu, Henan Province, China, include tortoise shells which are incised with signs – some of which anticipate later Chinese characters and may be intended as words. Is this the earliest writing? The authors decide rather that the signs in this very early period performed as symbols connected with ritual practice, but they presage a long period of sign use which led eventually to a writing system.

Source : Antiquity Volume 77, Issue 295, March 2003 , pp. 31-44

As described above, the symbols, which have not yet been deciphered, are believed to be an example of 'proto-writing'. They've been dated to around 6,000BC,

Also see : BBC news, 2003