The Flood story in Mesopotamia actually has several iterations, and it's hard to say which is the earliest. These are known as the Eridu Genesis, the Atrahasis Epic, and the Utnapishtim section of the various Gilgamesh Epics.

Some of the oldest mentions of the deluge are in the Sumerian King Lists, which are Old Babylonian texts from the early 2nd millennium documenting earlier Sumerian mythologizing of political succession. Several of these texts refer to one Ziusudra as the last king before "the flood swept over" and Kingship was disrupted. This corresponds with one of the three literary "flood stories": the Eridu Genesis. This version is known from three tablets: two in Sumerian from ~1600 BCE and one bilingual copy found in the much later library of Ashurbanipul, 7th century BCE. Note that these are just the dates of the tablets, and that the story itself (as in the case other two versions of the flood story as well) is probably much older, going back to the Sumerian period. The Eridu Genesis follows a basic template in common with the other Mesopotamian flood accounts; Mankind is created and organized into cities, their raucous noisiness disrupts the sleep of Enlil, god of the wind, who decides to destroy them. Enki, the god of fresh water and a proponent of humanity, warns the Priest-King Ziusudra of the impending cataclysm and instructs him to build a boat, preserve animals, and so on.

The Atrahasis Epic is an Akkadian version, nearly identical to and contemporaneous with the Ziusudra story, with tablets dating to the reign of Hammurabi's grandson Ammi-Saduqa in the late 1600s. Both Atrahasis and Ziusudra are inheritors of the king or eponymous city of Shuruppak. The final and most famous account is found in The Epic of Gilgamesh, the dating of which is all over the freaking place (seriously, there are so many fragments and alternate versions found over such broad periods of time that I'm having a hard time sorting it out) but with one definitive Akkadian version from the 7th century. In this telling, which seems to be adapted from Atrahasis with some minor changes, the story is framed within Gilgamesh's quest for immortality, in which he meets and interviews Utnapishtim, the long-lived survivor of the deluge (his name actual means "he who found longevity"). Long life spans are characteristic of the tale - Ziudrusa in the King Lists was reported to have reigned for 36,000 years or some such, a remarkable trait shared by his pre-deluvian predecessors. This points to one of the important literary functions of the flood myth: the demarcation of the mythic past from the historic era.

Thorkild Jacobsen suggests that the recurrent motif in some inscriptions of "after the flood swept the land" represents the cultural and political disruption of Sumerian society by the invasion of the nomadic Gutians and the subsequent collapse of the resurgent Third Dynasty of Ur at the hands of the Elamites. I'm not sure if that's a consensus interpretation, but it does seem consistent with other allegorical references in texts like The Lamentation of Ur, where the destruction wrought by invaders is described as "the storm of Enlil".

Ahem! I got so caught up in the textual mire that I almost forgot to address your question. There is archaeological evidence of localized flooding throughout the Jemdet-Nasr and Ubaid periods in Mesopotamia -especially at Shuruppak - which could constitute the source of a cultural "flood memory" (see this wikipedia page), amongst many other theories of widespread pre-historical flooding, but it's my understanding that there are significant difficulties with a coherent, synthesized account of evidence for deluvian historicity. In my opinion, it's more likely that flood myths are so prevalent across human cultures simply because flooding is such a universal experience. Millions of people have died in floods in just the last hundred years, and in the ancient past humanity was even more closely tied to rivers and coasts where they were at the constant mercy of nature's watery whims.

A lot of people try to claim parallels between disparate flood traditions across the globe, but in my opinion that view just doesn't hold water. I'm only really familiar with Mesopotamian, Chinese, and Australian flood stories, but in those cases the themes, details and methods are all vastly different. Of course, it IS quite likely that the biblical flood is derived from the other near eastern myths. Noah and Utnapashtim are practically interchangeable.