Chinese kids the world over are frequently taught that there is "5000 years of Chinese history". What basis is there for this claim?
The basis for the 5,000 years figure comes from tracing Chinese "history" to the Three Sovereigns and Five Emperors. This figure includes over 1,000 years of legends. The next 1000 years are semi-legendary, being only somewhat corroborated by historical evidence. We start to have fragmentary historical records for a few centuries after that, but true recorded history is generally held to have begun in the 8th century B.C., less than 2800 years ago.
Therefore, whether Chinese history is really 5,000 years is quite dependent on how broadly you want to define "history". I'll list a few of the major points here:
Contrary to the assertions of some, written history was very prominent in China long before the Tang dynasty. A strong culture of writing existed in Ancient China, as attested to most famously by extensive inscriptions on some 150,000 pieces of oracle bones found from the reign of King Wu Ding of Shang (1250-1192 B.C.) onward. Important documentation of historical events begin to appear en masse in inscriptions on bronzewares by the Chou Dynasty (770-255 B.C.).
Such archaeological sources provide corroboration for ancient history chronicles as well as primary information. The highly influential Han Dynasty Records of the Grand Historian by Ssuma Chhien (139–86 B.C.), for instance, provided a list of Shang Dynasty kings which were confirmed in the early 1900s by oracle bones excavated from Anyang. The oldest extant fragments of this text date from the Northern and Southern Dynasties period (A.D. 420-589).
Canonically, the oldest history text was the Classics of History. It was "edited" together by Confucius (551–479 B.C.) during the Spring and Autumn Era, from a collection of earlier works. The oldest existing copy is a set of excavated bamboo slips, dating from the mid-late Warring States Era (c. 305 B.C.).
Traditional versions of the Classics of History date from the Chin Dynasty (A.D. 265–420), after known original copies were destroyed during the Qin Dynasty's suppression, and the early Han Dynasty recreations lost in warfare. Notably, during this period a set of ancient historical annals were discovered in an old tomb: the Bamboo Annals. It appears to be the official history of the State of Wei (403–225 B.C.) from the Warring States era, and recounted history from pre-Xia Dynasty legends to the reign of King Hsiang (319–296 B.C.). Unfortunately most of its contents has been lost.
A notable example of a well-preserved ancient Chinese history manuscript comes from a set of annals contained in bamboo slips excavated from the tomb of a government official in Yúnmèng. The Shuihudi_Qin Annals recorded major events of the last century of the Warring States era, leading up to the conquest of the six eastern states by Qin. This set of annals were produced during the short lived Qin Dynasty (221-206 B.C.) and was part of an extensive collection that seemed to have helped the official (whose tomb it was found in) administer the Qin Qmpire's laws.
Major early Chinese historical writings (all dates approximate):
Well, to be factual, more like 4100 years+ of history is available for study. Xia Dynasty is dated back to cca 2100 BC - 1600 BC, numerous sites approves these dates. Before these days dates and historical records get more and more inaccurate and entering into the realm of legends. "5000 years" seems more like a generous rounding up, but it is not very far from reality.
Chinese history is well documented since their writing system of pictograms changed relatively few compared to the European, Middle-Eastern writing systems. So their historical documents in any form or shape still readable for researchers who studied the evolution of pictograms. To get the history recorded there is an important factor as well: China wasn't invaded many times by different cultures. Hereby I compare with Egyptian history: Kopt, Greek, Roman, Arabic, Colony eras are switching each other. In China they assimilated everybody they could, and only the Mongols could force them to knees as a country. Other than Mongols, Manchus could conquer China (and became a Dynasty in the row) and the imperial Japan managed to partially conquer China.
I like @Semaphore 's answer above. I'd like to clarify a little:
What kind of history are you asking about?
There is an important distinction between recorded history and pre-history. Generally speaking, when people speak about history, they are referring to recorded history, which requires the answer to be no, Chinese history is between 2,500 and 4,000 years old, depending on how reliable you view the source material.
Pre-history relies more on legends, oral history, and archeology. Chinese pre-history extends at least 10,000 years - to at least 8,000 BCE. For example, the domestication of millet occurred about 12,000 years ago, as shown by an archeological site containing >50,000 kg of millet in storage containers. This article (which I find interesting) give the details about an ancient neolithic agricultural community, that had evidently existed for some time prior to their storage of these vast quantities of grain.
So we have about 12,000 y.b.p. as a starting date for agriculture. People were living in this region at least 750,000 years before that! So when did pre-history begin?
History, however, relies to a great deal on written records. The written history for the warring states period 476 - 221 BCE., is very strong. So it can be agreed that History in China is more than 2500 years old (2015-476 ~ 2500 years).
Written history before this time becomes less historical and more legendary. Certainly the Zhou dynasty information is more factual, and again, @Semaphore's answer speak very well about the historocity of the Shang. The older history includes something like this:
Of course, this is an extreme example. See this SE question. I think a reasonable start to Chinese recorded history is 4000 years before present. Either way, Chinese recorded history is between 2500 and 5000 years old, depending on your view of the source material.
It is very difficult to find any Chinese historical writing that is not a copy which is verifiably earlier than the Tang dynasty (about 700 A.D.). The Nestorian Stele (781 A.D.) is one of the earliest known historical documents written in Chinese. There are some earlier writings, such as copies of the Analects of Confucius on stone supposedly dating to around 175 A.D., however, these are philosophical writings, not history.
There is a historical tradition in China which dates back far before the Tang dynasty and was primarily oral, but it is difficult to know how much of it is has any basis in reality. The Chinese routinely made up "facts" of various kinds and ascribed them to ancient "historians" and this practice was considered normal and acceptable. It is more or less impossible to verify anything before the Tang dynasty because there are no stone inscriptions comparable to those we have for Egypt, Greece, Babylon, Sumaria etc. Even verifying events from the Tang dynasty is difficult.
What is clear is that before the Tang dynasty, writing was very rare and Chinese society was illiterate. We know this because all the tombs and other ancient sites before the Tang dynasty never have any inscriptions. For example, the famous Terra Cotta Army of the emperor conventionally dated to the 3rd century B.C. is gigantic, yet contains no inscriptions or writing whatsoever (except inventory marks on the weapons), and as a rule other such sites before the Tang dynasty are the same way.
China had a very strong oral tradition which continued right into the 20th century. It was required of students to memorize and be able to recite long passages from Confucius and other philosophers. History was much less important, but was apparently memorized in the same way. Unfortunately, cultural upheavals and evolution affect such traditions, which has left pre-Tang history in a very uncertain state.